permutations

Напиши сам.
Идея такая.
Как делается вывод всех перестановок списка из неравных элементов? Мы на первое место списка ставим какой-нибудь элемент, а потом присобачиваем к нему все возможные перестановки уже меньшего множества элементов.

Теперь входные данные — это не список, а словарь (например), где ключу «элемент списка» соответствует число его вхождений в список.
Теперь же нужно будет перебирать ключи, и к ним прицеплять перестановки, сгенерённые для словаря с убавленным на 1 значением у этого ключа (ну или удалённым ключом-значением).

Получилось ли у меня ясно выразиться?

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

Не надо их таскать. Да, будет рекурсия, ну и что?

Напиши ещё коротенькую функцию «прибавить данный элемент ко всем элементам данного списка списков».

Вот подают тебе словарь на вход.
Проверяем, не слишком ли он короткий, если он вида {x:k}, то мы уже знаем ответ.
Если не слишком короткий, то заводим список из всех неравных элементов (они же ключи в словаре), потом для каждого элемента этого списка генеришь свой список перестановок (на основе словаря уже меньшей «мощности»), потом всё склеиваешь как надо.

Памяти будет кушать столько, что вложения в 16Гб-модули станут актуальными :))

Ну то есть это решение не то чтобы очень быстрое, и в каждой функции O(n) рекурсивных вызовов. Плохо, не правда ли? Но я не умею лучше.

Ога. Но у меня в голове не очень укладывается, как достать список для склеивания, если на вход подается словарь? Следовательно, и возвращается тоже словарь(а на основе одного словаря может быть много списков). Может, накидаешь черновой вариант?

Самый тупой вариант - вынести все повторы set-ом.

Нет-нет. Возвращаем список списков. Ниже некий псевдокод:

def perm(d):
  if (есть ключи с нулевым значением):
    убрать эти ключи
  if (словарь вида {x:k}):
    return [[x,...,x]]
  result = []
  for x in d:
    dx = d
    dx[x] = dx[x]-1
    permx = perm(dx)
    permx = addfirst(x, permx)
    result = result + permx
  return result

Да, точно работать зато будет. Но долго, и быдлокодинг.

import itertools

l = ['a', 'b', 'c']

for order in itertools.permutations(range(len(l))):
    print([l[i] for i in order])

Оно?

http://blog.bjrn.se/2008/04/lexicographic-permutations-using.html

Ну то есть всё равно вычислять все перестановки вместе с кучей повторов? долго.

Нет. Прочитал внимательнее - не оно.

Заработало?

In [60]: list(combo.next_permutation(17*[True]+[False]))
Out[60]: 
[[True,
  True,
  True,
  True,
  True,
  True,
  True,
  True,
  True,
  True,
  True,
  True,
  True,
  True,
  True,
  True,
  True,
  False]]

по ссылке - нет. Свою писать буду если совсем припрет.

А вы пробовали по ссылке почитать? Например, узнать, что такое pred?

а, все, понял.

Пред тоже, но скорее нужно узнать, что такое next_permutation в контексте отсортированных перестановок.

Для получения всех проще всего прогнать его с pred=cmp и с pred=(lambda x:-cmp(x)), выкинув один из первых элементов.

python все же бывает коварен =(

for l in next_permutation([1, 1, 2, 2]):
    print l

[1, 1, 2, 2]
[1, 2, 1, 2]
[1, 2, 2, 1]
[2, 1, 1, 2]
[2, 1, 2, 1]
[2, 2, 1, 1]

Но

[l for l in next_permutation([1, 1, 2, 2])]

[[2, 2, 1, 1],
 [1, 2, 1, 2],
 [1, 2, 2, 1],
 [2, 1, 1, 2],
 [2, 1, 2, 1],
 [2, 2, 1, 1]]

Автор реализации алгоритма по ссылке что-то подозревал...

Ошибка в первом yeild там тоже надо сделать копию списка (yeild seq[:])