комбинации с повторениями в python

Question

Моя задача - написать функцию, которая возвращает все последовательности длины n, включая числа в диапазоне от A до B, где {A1 < = A2 < = A3 < = ... < = An} Например, если A = 1 B = 3 n = 2, он должен вернуться [[1,1], [1,2], [1,3], [2,2], [2,3], [3 ., 3]] Я должен использовать рекурсию и список понимание, и не может использовать itertools (я знаю, что это не имеет смысла) .My мысль была:

def combinations(L,len): #L is list [A,A+1, ... ,B] 
    if len == 1: 
     return L 
    return [[a,b] for a in L for b in combinations(L,len-1) if b>=a] 

, но он не работает при п> 2 Может ли кто-нибудь дать мне несколько намеков?

Answer 1

Пара наблюдения:

1. Если len является 1, вы хотите, чтобы вернуться [[A], [A + 1], ..., [B]], а не [A, A +1, ..., B], как и у вас. Итак, вам нужно обернуть значение в свой собственный список, а не просто вернуть L, правильно?

2. В другом случае, когда len не является 1, [a,b] будет хранить список вложенности, например. [x,[x,[x...]]]. Поэтому вместо [a,b] используйте [a]+b. Это не сработает, пока вы не исправите базовый случай, как описано выше.

3. Избавьтесь от теста b>=a. Это не имеет никакого смысла. b - это список, так как вы можете сравнить его с a, и почему бы вам даже этого захотелось?

4. Вместо этого, при рекурсии, не проходите L. Передайте ему новый L, членами которого являются все >= a. В качестве альтернативы вы можете просто использовать A и B в качестве аргументов и избавиться от L. Тогда вы можете использовать range в своих целях.

Answer 2

Я не могу понять, рекурсивным, здесь является альтернативой

#!/usr/bin/python 
def combinations(L,length): #L is list [A,A+1, ... ,B] 
    length_L = len(L) 
    L_new=[] 
    for start in range(0,length_L): 
     if length > 1: 
      unit_self = retrieve_unit_self(L, start,length) 
      L_new.append(unit_self) 
     if start + length <= length_L: 
      unit = retrieve_unit(L, start,length) 
      L_new.append(unit) 
    return L_new; 
def retrieve_unit_self(L,start,length): 
    unit=[] 
    for index in range(0,length): 
     unit.append(L[start]) 
    return unit 
def retrieve_unit(L,start,length): 
    unit=[] 
    for index in range(0,length): 
     unit.append(L[index+start]) 
    return unit 
def main(): 
    L = ['a','b','c'] 
    L_new = combinations(L,1) 
    print L_new 
    L_new = combinations(L,2) 
    print L_new 
    L_new = combinations(L,3) 
    print L_new 
    L_new = combinations(L,4) 
    print L_new 
if __name__ == '__main__': 
    main() 

Результат:

./list.py 
[['a'], ['b'], ['c']] 
[['a', 'a'], ['a', 'b'], ['b', 'b'], ['b', 'c'], ['c', 'c']] 
[['a', 'a', 'a'], ['a', 'b', 'c'], ['b', 'b', 'b'], ['c', 'c', 'c']] 
[['a', 'a', 'a', 'a'], ['b', 'b', 'b', 'b'], ['c', 'c', 'c', 'c']]