Recursive permutation without loops or itertools-CodePudding

Searched the entire web for a solution, couldn't find anything.
Need some help figuring out the algorithm, getting all the permutations with repetitions.
I'm not allowed to use loops or any other helper libraries.

def func(num):
    # The solution

The num, represents the number of each node length.

For example, if num=1, the solution would be ['a', 'b', 'c']
or if num=2, then ['aa', 'ab', 'ac', 'ba', 'bb', 'bc', 'ca', 'cb', 'cc'], etc

Thank you

CodePudding user response：

You can use a recursive generator function:

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)])

Output:

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

CodePudding user response：

We can write combinations that accepts any iterable, t, to compute fixed-length combinations of any integer size, 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)

Any iterable can be used as input. Combinations treats "abc" equivalent to ["a", "b", "c"] in this case -

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

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

It works for all positive integer values of n -

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

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

And produces an empty output when n = 0 or n < 0 -

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

()

Using a tuple as the accumulator, combinations is not limited to string-based combinations only. The caller can easily join the tuple to create two-char strings, if desired -

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

aa
ab
ac
bb
bc
cc

CodePudding user response：

Please try this -

input = [‘a’,’b’,’c’]
elements=Len(input)
output = [ ]

def func(t):
        global input
        global output    
        if t==1:
            print(input)    
        if t>1:
             Func1(0,0)
             input=output 
             func(t-1)


Def func1(x,y):
        global input
        global output    
        if y<Elements:
           output.append(input[x] input[y])
           func1(x,y 1)    
        if y 1>Elements and x 1<Elements:
           func1(x 1,0)    
        return input[x]

func(2)

Displaying the Output:

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