Есть ли способ генерировать все уникальные перестановки списка элементов - PullRequest
Новая
       39

Есть ли способ генерировать все уникальные перестановки списка элементов

3 голосов
/ 24 мая 2019

У меня есть список из пяти атрибутов, каждый атрибут имеет пять разных значений. Я хочу сгенерировать их декартово произведение и отфильтровать все уникальные перестановки.

Некоторый фон:

Мне нужно, чтобы они были моими входными значениями для решения логической головоломки. Где я проверяю правила против них, чтобы найти правильное решение. 

from itertools import product

# input
names = ['Dana', 'Ingo', 'Jessica', 'Sören', 'Valerie']
ages = [26, 27, 30, 33, 35]
tops = ['Blouse', 'Poloshirt', 'Pullover', 'Sweatshirt', 'T-Shirt']
colors = ['blue', 'yellow', 'green', 'red', 'black']
sizes = ['XS', 'S', 'M', 'L', 'XL']

all_attributes = [names, ages, tops, colors, sizes]

# cartesian product (superset)
inputs = list(product(*all_attributes))

# the following code you do that...

Возможно, упрощенный пример может прояснить ситуацию.

Данные: 

[['Dana', 'Ingo'], [26, 27]]

Декартово произведение данных: 

[('Dana', 26), ('Dana', 27), ('Ingo', 26), ('Ingo', 27)]

Что я хочу: 

[[('Dana', 26), ('Ingo', 27)],
 [('Dana', 27), ('Ingo', 26)],
 [('Ingo', 26), ('Dana', 27)],
 [('Ingo', 27), ('Dana', 26)]]

Чего я не хочу: 

[[('Dana', 26), ('Ingo', 26)], ...

Я не хочу, чтобы несколько вхождений одного и того же значения. Место имеет значение, поэтому оно должно иметь перестановочный характер и то же самое для списка списков с пятью элементами. Я предполагаю, что размер вывода будет огромным и, возможно, это невозможно вычислить, поэтому было бы неплохо указать некоторые значения мест, которые являются фиксированными. Например, я хочу установить «Дана» в качестве имени первого элемента.

Выход: 

[[('Dana', 26), ('Ingo', 27),
 [('Dana', 27), ('Ingo', 26)]]

Может быть, вы из любопытства можете сказать, какие конкретные математические названия для понятий, которые мне нужны?

Загадка:

Есть пять друзей (Дана, Инго, Джессика, Сорен, Валери) , ожидающих в очереди на кассе торгового центра. Они все разного возраста (26, 27, 30, 33, 35) и хотят купить разные топы (блуза, поло, пуловер, толстовка, футболка) для себя , Вершины имеют разные цвета (синий, желтый, зеленый, красный, черный) и размеры (XS, S, M, L, XL) .

Правила:

  1. Топ "Дана" хочет купить это "XL". Позади нее (но не прямо позади) - кто-то с «черным» топом.
  2. «Джессика» ждет прямо перед человеком, который хочет купить «Поло-рубашку».
  3. Второй человек в очереди хочет купить «желтый» топ.
  4. «Футболка» не «красная».
  5. «Сёрен» хочет купить «Толстовку». Человек, который ждет прямо перед ним, старше, чем тот, кто позади него.
  6. «Инго» нужен топ размером «L».
  7. Последнему человеку в очереди 30 лет.
  8. Старейший собирается купить топ с наименьшим размером.
  9. Человек, который ждет прямо за «Валери», хочет купить «красный» топ, который больше, чем размер «S».
  10. Самый молодой человек хочет купить «желтый» топ.
  11. Джессика собирается купить «Блузку».
  12. Третий, ожидающий в очереди, хочет купить топ размера «М».
  13. Poloshirt - это «красный», «желтый» или «зеленый».

Ответы [ 2 ]

2 голосов
/ 24 мая 2019

Это сделает это, но займет очень много времени.Я сократил размер списка, потому что ваши параметры по запросу имеют 24 883 200 000 перестановок: 

from itertools import permutations, product

names = ['Dana', 'Ingo']
ages = [26, 27]
tops = ['Hemd', 'Poloshirt']
colors = ['blau', 'gelb']
sizes = ['XS', 'S']

options = []

# Generate the Cartesian product of all permutations of the options.
for name,age,top,color,size in product(*map(permutations,[names,ages,tops,colors,sizes])):
    # Build the option list. zip() transposes the individual lists.
    option = list(zip(name,age,top,color,size))
    options.append(option)
    print(option)

Вывод: 

[('Dana', 26, 'Hemd', 'blau', 'XS'), ('Ingo', 27, 'Poloshirt', 'gelb', 'S')]
[('Dana', 26, 'Hemd', 'blau', 'S'), ('Ingo', 27, 'Poloshirt', 'gelb', 'XS')]
[('Dana', 26, 'Hemd', 'gelb', 'XS'), ('Ingo', 27, 'Poloshirt', 'blau', 'S')]
[('Dana', 26, 'Hemd', 'gelb', 'S'), ('Ingo', 27, 'Poloshirt', 'blau', 'XS')]
[('Dana', 26, 'Poloshirt', 'blau', 'XS'), ('Ingo', 27, 'Hemd', 'gelb', 'S')]
[('Dana', 26, 'Poloshirt', 'blau', 'S'), ('Ingo', 27, 'Hemd', 'gelb', 'XS')]
[('Dana', 26, 'Poloshirt', 'gelb', 'XS'), ('Ingo', 27, 'Hemd', 'blau', 'S')]
[('Dana', 26, 'Poloshirt', 'gelb', 'S'), ('Ingo', 27, 'Hemd', 'blau', 'XS')]
[('Dana', 27, 'Hemd', 'blau', 'XS'), ('Ingo', 26, 'Poloshirt', 'gelb', 'S')]
[('Dana', 27, 'Hemd', 'blau', 'S'), ('Ingo', 26, 'Poloshirt', 'gelb', 'XS')]
[('Dana', 27, 'Hemd', 'gelb', 'XS'), ('Ingo', 26, 'Poloshirt', 'blau', 'S')]
[('Dana', 27, 'Hemd', 'gelb', 'S'), ('Ingo', 26, 'Poloshirt', 'blau', 'XS')]
[('Dana', 27, 'Poloshirt', 'blau', 'XS'), ('Ingo', 26, 'Hemd', 'gelb', 'S')]
[('Dana', 27, 'Poloshirt', 'blau', 'S'), ('Ingo', 26, 'Hemd', 'gelb', 'XS')]
[('Dana', 27, 'Poloshirt', 'gelb', 'XS'), ('Ingo', 26, 'Hemd', 'blau', 'S')]
[('Dana', 27, 'Poloshirt', 'gelb', 'S'), ('Ingo', 26, 'Hemd', 'blau', 'XS')]
[('Ingo', 26, 'Hemd', 'blau', 'XS'), ('Dana', 27, 'Poloshirt', 'gelb', 'S')]
[('Ingo', 26, 'Hemd', 'blau', 'S'), ('Dana', 27, 'Poloshirt', 'gelb', 'XS')]
[('Ingo', 26, 'Hemd', 'gelb', 'XS'), ('Dana', 27, 'Poloshirt', 'blau', 'S')]
[('Ingo', 26, 'Hemd', 'gelb', 'S'), ('Dana', 27, 'Poloshirt', 'blau', 'XS')]
[('Ingo', 26, 'Poloshirt', 'blau', 'XS'), ('Dana', 27, 'Hemd', 'gelb', 'S')]
[('Ingo', 26, 'Poloshirt', 'blau', 'S'), ('Dana', 27, 'Hemd', 'gelb', 'XS')]
[('Ingo', 26, 'Poloshirt', 'gelb', 'XS'), ('Dana', 27, 'Hemd', 'blau', 'S')]
[('Ingo', 26, 'Poloshirt', 'gelb', 'S'), ('Dana', 27, 'Hemd', 'blau', 'XS')]
[('Ingo', 27, 'Hemd', 'blau', 'XS'), ('Dana', 26, 'Poloshirt', 'gelb', 'S')]
[('Ingo', 27, 'Hemd', 'blau', 'S'), ('Dana', 26, 'Poloshirt', 'gelb', 'XS')]
[('Ingo', 27, 'Hemd', 'gelb', 'XS'), ('Dana', 26, 'Poloshirt', 'blau', 'S')]
[('Ingo', 27, 'Hemd', 'gelb', 'S'), ('Dana', 26, 'Poloshirt', 'blau', 'XS')]
[('Ingo', 27, 'Poloshirt', 'blau', 'XS'), ('Dana', 26, 'Hemd', 'gelb', 'S')]
[('Ingo', 27, 'Poloshirt', 'blau', 'S'), ('Dana', 26, 'Hemd', 'gelb', 'XS')]
[('Ingo', 27, 'Poloshirt', 'gelb', 'XS'), ('Dana', 26, 'Hemd', 'blau', 'S')]
[('Ingo', 27, 'Poloshirt', 'gelb', 'S'), ('Dana', 26, 'Hemd', 'blau', 'XS')]
1 голос
/ 31 мая 2019

Существует фундаментальная проблема с подходом использования перестановок для типа логической головоломки, которая у вас есть.Проблема даже не в том, что их так много, что ваш решатель вряд ли закончит в разумные сроки.Проблема заключается в том, что у вас нет автоматизированного способа проверки правил на предмет этой проблемы: все возможности, стоящие перед вами, не имеют смысла, если у вас нет способа их проверить.

Чтобы решить эти проблемы,Я создал проект под названием Puzzle Solvers:

Это небольшой проект, который в настоящее время содержит один класс интересов: puzzle_solvers.elimination.Solver.Этот класс реализует большинство операций, необходимых для решения проблемы типа процесса исключения, представленной в вашем вопросе.Вся логика задокументирована , а учебник - это пошаговое решение вашей конкретной проблемы.Я объясню основы здесь, чтобы вы могли понять, что я сделал, и, возможно, улучшить его.

Шаг 1 - признать, что позиция в очереди является таким же атрибутом, как возраст, имя и т. Д. Это означает, чтопорядок больше не актуален.

Шаг 2 - признать, что это скрытая проблема с графиком.У вас есть 30 узлов: все возможные атрибуты (шесть из них) каждого из пяти человек.График начинается почти полностью.Отсутствуют только ребра между атрибутами данного типа, поэтому вы начинаете с 375. Вместо полных 435.

Конечная цель - получить одно ребро между каждым классом атрибута среди пяти связанных компонентов в графе.,Таким образом, конечное число ребер равно 5 * 15 = 75.

Итак, как вы удаляете ребра?Простые правила, такие как «Футболка» не «красная», довольно просты: просто удалите этот край.Правила типа «Последний человек в очереди 30 лет».также просты и более выгодны с точки зрения удаления кромок.Все ребра между возрастами, которые не 30 и позиция 5, удалены, а также все ребра между позициями, которые не 5 и 30 лет. Я добавил пару полуобожженных служебных упаковщиков, чтобы проверить условия больше и меньше, иудалить ребра, которые представляли невозможные комбинации.

Наиболее важным аспектом решателя является тот факт, что каждый раз, когда ребро удаляется, оно полностью выполняет все логических последствий этой операции.,Представьте, что у вас есть «Полошира» - это «красный», «желтый» или «зеленый» »и что вы достигли точки в своей головоломке, где ни один из этих трех цветов не связан с 30 лет. Это означает, что тот, ктоносить поло-рубашку нельзя с 30 лет.На самом деле «Poloshirt» не может иметь любых ребер с конечными точками, которые не разделяются этими тремя цветами.Если вы рекурсивно выполните эти выводы, вы получите полное решение.

Извините за бесстыдную продажу моей посылки, но в оправдание я написал ее просто для того, чтобы ответить на этот вопрос.

...