Как перенести n элементов из списка рекурсивно в python?

Question

Я пытаюсь понять, как создать рекурсивно все возможные перестановки n из списка.

Например результат n=2 и list=[0,1,5] будет:

[[0, 0], [1, 0], [5, 0], [0, 1], [1, 1], [5, 1], [0, 5], [1, 5], [5, 5]] 

или n=3 и list=[2,3]:

[[2, 2, 2], [3, 2, 2], [2, 3, 2], [3, 3, 2], [2, 2, 3], [3, 2, 3], [2, 3, 3], [3, 3, 3]] 

(вроде как декартово произведение).

мне удалось придумать этот кусок кода:

def perm(nlist, m): 

    if m > len(nlist): 
     return 
    if m == 0 or m == len(nlist): 
     return [[]] 
    results = []    
    for list_i in nlist: 
     temp = list(nlist)   
     temp.remove(list_i) 
     results.extend(map(lambda x: [list_i] + x, perm(temp, m-1))) 
    return results 

, но это не дает перестановкам как [0,0] [1,1] [2,2] и т.д.

ли кто-нибудь есть решение для меня?

Как это сделать без использования map() и lambda()?

Answer 1

Это не вид как декартово произведение; это точно как декартова продукт.

>>> from itertools import product 
>>> list(product([0,1,5], repeat=2)) 
[(0, 0), (0, 1), (0, 5), (1, 0), (1, 1), (1, 5), (5, 0), (5, 1), (5, 5)] 
>>> list(product([2,3], repeat=3)) 
[(2, 2, 2), (2, 2, 3), (2, 3, 2), (2, 3, 3), (3, 2, 2), (3, 2, 3), (3, 3, 2), (3, 3, 3)] 

polyfill для itertools.product является следующее:

def product(*args, **kwds): 
    # product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy 
    # product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111 
    pools = map(tuple, args) * kwds.get('repeat', 1) 
    result = [[]] 
    for pool in pools: 
     result = [x+[y] for x in result for y in pool] 
    for prod in result: 
     yield tuple(prod) 

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

def cartesian_exponent(li, e=1): 
    pools = [li] * e 
    result = [[]] 
    for pool in pools: 
     result = [x+[y] for x in result for y in pool] 
    return result 

Или рекурсивно используя еще один непонятный список понимание:

def cartesian_exponent(li, e=1): 
    if e == 1: 
     return [[x] for x in li] 
    else: 
     return [[x]+y for x in li for y in cartesian_exponent(li, e=e-1)] 

который может быть сжат в одну строку :

def cartesian_exponent(li, e=1): 
    return [[x] for x in li] if e == 1 else [[x] + y for x in li for y in cartesian_exponent(li, e=e-1)] 

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

Некоторые тесты:

>>> cartesian_exponent([0,1,5], e=2) 
[[0, 0], [0, 1], [0, 5], [1, 0], [1, 1], [1, 5], [5, 0], [5, 1], [5, 5]] 
>>> cartesian_exponent([2,3], e=3) 
[[2, 2, 2], [2, 2, 3], [2, 3, 2], [2, 3, 3], [3, 2, 2], [3, 2, 3], [3, 3, 2], [3, 3, 3]] 

Answer 2

В результате вы получите Cartesian product, который является множеством всех упорядоченных пар (a, b), где a ∈ A и b ∈ B. Или все перестановки всех комбинаций.

from itertools import combinations_with_replacement as iter_combs 
from itertools import permutations 

def perms_combs(l, n): 
    all_combs = [] 
    for l in list(iter_combs(l, n)): 
      [all_combs.append(perm) for perm in list(permutations(l, n))] 
    return list(set(all_combs)) 

>> print list(product([0, 1, 5], repeat=2)) 
    [(0, 0), (0, 0), (0, 1), (1, 0), (0, 5), (5, 0), (1, 1), (1, 1), (1, 5), (5, 1), (5, 5), (5, 5)] 

>> print list(product([2, 3], repeat=3)) 
    [(3, 3, 3), (2, 2, 2), (2, 3, 2), (3, 3, 2), (2, 3, 3), (3, 2, 2), (3, 2, 3), (2, 2, 3)] 

Этот процесс, однако, уже покрыта функциями itertools: product

from itertools import product 

>> print product([0, 1, 5], 2) 
    [(0, 0), (0, 0), (0, 1), (1, 0), (0, 5), (5, 0), (1, 1), (1, 1), (1, 5), (5, 1), (5, 5), (5, 5)] 

>> print product([2, 3], 3) 
    [(3, 3, 3), (2, 2, 2), (2, 3, 2), (3, 3, 2), (2, 3, 3), (3, 2, 2), (3, 2, 3), (2, 2, 3)]