没有循环或 itertools 的递归排列

Question

在整个网络上搜索解决方案，找不到任何东西。
需要一些帮助来弄清楚算法，通过重复获得所有排列。
我不允许使用循环或任何其他辅助库。

def func(num):
    # The solution

num，表示每个结点的长度。

例如，如果 num=1，解决方案将是 ['a', 'b', 'c']
或者如果 num=2，则 ['aa', 'ab', 'ac', 'ba', 'bb', 'bc', 'ca', 'cb', 'cc']，等等

谢谢

Answer 1

您可以使用递归生成器函数：

vals = ['a', 'b', 'c']
def combos(d, n, c = ''):
   if len(c) == n:
       yield c
   else:
       def _range(x=0):
          if x < len(d):
              yield from combos(d, n, c=c+d[x])
              yield from _range(x+1)
       yield from _range()

print([*combos(vals, 2)])

输出：

['aa', 'ab', 'ac', 'ba', 'bb', 'bc', 'ca', 'cb', 'cc']

Answer 2

我们可以编写 combinations 接受任何迭代，t，计算任何整数大小的固定长度组合，n -

def combinations(t, n):
  if n <= 0:
    yield ()
  elif not t:
    return
  else:
    for x in combinations(t, n - 1):
      yield (t[0], *x)
    yield from combinations(t[1:], n)

任何可迭代对象都可以用作输入。在这种情况下，组合将 "abc" 等同于 ["a", "b", "c"] -

for x in combinations("abc", 2):
  print(x)

('a', 'a')
('a', 'b')
('a', 'c')
('b', 'b')
('b', 'c')
('c', 'c')

它适用于 n -

的所有正整数值

for x in combinations("abc", 1):
  print(x)

('a',)
('b',)
('c',)

并在 n = 0 或 n < 0 -

时产生空输出

for x in combinations("abc", 0):
  print(x)

()

使用元组作为累加器，combinations 不仅限于基于字符串的组合。如果需要，调用者可以轻松加入元组以创建双字符字符串 -

for x in combinations("abc", 2):
  print("".join(x))

aa
ab
ac
bb
bc
cc

Answer 3

函数 func(n) 和 func1(list1,list2) 将生成排列。函数 func1 将对乘以 n 次。当 n=1 时，(a,b,c)。那么当n=2时，(a,b,c) x (a,b,c)。当 n=3 时，(a,b,c) ^ 3 .

input = ['a','b','c']
input2 = input
output = [ ]

def func(t):
        global input
        global input2
        global output
        if t==1:
            print(input)    
        if t>1:
             func1(0,0)
             input=output 
             output=[]
             func(t-1)

def func1(x,y):
        global input
        global input2
        global output
        if y<len(input):
           output.append(input2[x]+input[y])
           func1(x,y+1)    
        if y+1>len(input) and x+1<len(input2):
           func1(x+1,0)    
        return input[x]

func(2)

显示 func(2):

时的输出

['aa', 'ab', 'ac', 'ba', 'bb', 'bc', 'ca', 'cb', 'cc']

没有循环或 itertools 的递归排列

Recursive permutation without loops or itertools

python

recursion

permutation

backtracking