Как и большинство интересных проблем, ваш вопрос имеет несколько решений. Алгоритм, который я написал (ниже), является самой простой вещью, которая пришла на ум.
Мне было проще подумать о проблеме, подобной дереву: первая группа, корень, имеет дочерний элемент для каждого содержащегося в нем номера, где каждый ребенок является второй группой. Вторая группа имеет дочернюю группу третьей группы для каждого числа, которое она содержит, у третьей группы есть ребенок четвертой группы для каждого числа, которое она содержит, и т. Д. Все, что вам нужно сделать, это найти все допустимые пути от корня до листьев.
Однако для многих групп с большим количеством чисел этот подход окажется медленным без каких-либо эвристик. Одна вещь, которую вы можете сделать, - сначала отсортировать список групп по размеру группы, наименьшей группе. Это был бы быстрый подход, который, в общем, обнаружил бы, что перестановка недействительна раньше, чем позже. Look-ahead, arc-consistency, и обратное отслеживание - это другие вещи, о которых вы могли бы подумать. [К сожалению, я могу включить только одну ссылку, потому что это мой первый пост, но вы можете найти эти вещи в Википедии.]
## Algorithm written in Python ##
## CodePad.org has a Python interpreter
Group1 = [1,2,3] ## Within itself, each group must be composed of unique numbers
Group2 = [2,3,4]
Group3 = [3,4,5]
Groups = [Group1,Group2,Group3] ## Must contain at least one Group
Permutations = [] ## List of valid permutations
def getPermutations(group, permSoFar, nextGroupIndex):
for num in group:
nextPermSoFar = list(permSoFar) ## Make a copy of the permSoFar list
## Only proceed if num isn't a repeat in nextPermSoFar
if nextPermSoFar.count(num) == 0:
nextPermSoFar.append(num) ## Add num to this copy of nextPermSoFar
if nextGroupIndex != len(Groups): ## Call next group if there is one...
getPermutations(Groups[nextGroupIndex], nextPermSoFar, nextGroupIndex + 1)
else: ## ...or add the valid permutation to the list of permutations
Permutations.append(nextPermSoFar)
## Call getPermutations with:
## * the first group from the list of Groups
## * an empty list
## * the index of the second group
getPermutations(Groups[0], [], 1)
## print results of getPermutations
print 'There are', len(Permutations), 'valid permutations:'
print Permutations
Стоимость расходов? –
Это похоже на интересный вопрос, но я не могу сделать головы или хвосты. Как вы думаете, вы можете отредактировать его, чтобы объяснить более подробно, возможно, включая ссылки на некоторые из более технических терминов? – rmeador