Как сгенерировать все перестановки списка в Python
Вы должны использовать символ обратного тика (`), например:
create table if not exists misc_info (
id INTEGER PRIMARY KEY AUTO_INCREMENT NOT NULL,
`key` TEXT UNIQUE NOT NULL,
value TEXT NOT NULL)ENGINE=INNODB;
5 ответов
Запуск с Python 2.6 (и если Вы находитесь на Python 3) Вы имеете стандартная библиотека инструмент для этого: itertools.permutations .
import itertools
list(itertools.permutations([1, 2, 3]))
, Если Вы используете более старый Python (< 2.6) по некоторым причинам или просто любопытны знать, как это работает, вот один хороший подход, проявленный от http://code.activestate.com/recipes/252178/ :
def all_perms(elements):
if len(elements) <=1:
yield elements
else:
for perm in all_perms(elements[1:]):
for i in range(len(elements)):
# nb elements[0:1] works in both string and list contexts
yield perm[:i] + elements[0:1] + perm[i:]
Несколько альтернативных подходов перечислены в документации itertools.permutations. Вот тот:
def permutations(iterable, r=None):
# permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC
# permutations(range(3)) --> 012 021 102 120 201 210
pool = tuple(iterable)
n = len(pool)
r = n if r is None else r
if r > n:
return
indices = range(n)
cycles = range(n, n-r, -1)
yield tuple(pool[i] for i in indices[:r])
while n:
for i in reversed(range(r)):
cycles[i] -= 1
if cycles[i] == 0:
indices[i:] = indices[i+1:] + indices[i:i+1]
cycles[i] = n - i
else:
j = cycles[i]
indices[i], indices[-j] = indices[-j], indices[i]
yield tuple(pool[i] for i in indices[:r])
break
else:
return
И другой, на основе itertools.product:
def permutations(iterable, r=None):
pool = tuple(iterable)
n = len(pool)
r = n if r is None else r
for indices in product(range(n), repeat=r):
if len(set(indices)) == r:
yield tuple(pool[i] for i in indices)
Это решение реализует генератор, чтобы не содержать все перестановки на памяти:
def permutations (orig_list):
if not isinstance(orig_list, list):
orig_list = list(orig_list)
yield orig_list
if len(orig_list) == 1:
return
for n in sorted(orig_list):
new_list = orig_list[:]
pos = new_list.index(n)
del(new_list[pos])
new_list.insert(0, n)
for resto in permutations(new_list[1:]):
if new_list[:1] + resto <> orig_list:
yield new_list[:1] + resto
Следующий код является оперативной перестановкой данного списка, реализованного как генератор. Так как это только возвращает ссылки на список, список не должен быть изменен вне генератора. Решение нерекурсивно, так использование низкая память. Работа хорошо также с несколькими копиями элементов во входном списке.
def permute_in_place(a):
a.sort()
yield list(a)
if len(a) <= 1:
return
first = 0
last = len(a)
while 1:
i = last - 1
while 1:
i = i - 1
if a[i] < a[i+1]:
j = last - 1
while not (a[i] < a[j]):
j = j - 1
a[i], a[j] = a[j], a[i] # swap the values
r = a[i+1:last]
r.reverse()
a[i+1:last] = r
yield list(a)
break
if i == first:
a.reverse()
return
if __name__ == '__main__':
for n in range(5):
for a in permute_in_place(range(1, n+1)):
print a
print
for a in permute_in_place([0, 0, 1, 1, 1]):
print a
print
И в Python 2.6 вперед:
import itertools
itertools.permutations([1,2,3])
(возвратился как генератор. Используйте list(permutations(l)) для возврата как список.)
следующий код с Python 2.6 и выше [ТОЛЬКО 116]
Первый, импортируйте itertools:
import itertools
Перестановка (заказывают вопросы):
print list(itertools.permutations([1,2,3,4], 2))
[(1, 2), (1, 3), (1, 4),
(2, 1), (2, 3), (2, 4),
(3, 1), (3, 2), (3, 4),
(4, 1), (4, 2), (4, 3)]
Комбинация (порядок НЕ имеет значения):
print list(itertools.combinations('123', 2))
[('1', '2'), ('1', '3'), ('2', '3')]
Декартово произведение (с несколькими iterables):
print list(itertools.product([1,2,3], [4,5,6]))
[(1, 4), (1, 5), (1, 6),
(2, 4), (2, 5), (2, 6),
(3, 4), (3, 5), (3, 6)]
Декартово произведение (с одним повторяемым и им):
print list(itertools.product([1,2], repeat=3))
[(1, 1, 1), (1, 1, 2), (1, 2, 1), (1, 2, 2),
(2, 1, 1), (2, 1, 2), (2, 2, 1), (2, 2, 2)]
-
1That' s странный. Что происходит, если Вы бросаете его в GrailsDomainClass, например,
((GrailsDomainClass)domainObject).persistentProperties? – Rob Hruska 29 December 2010 в 20:13