CODEWITHSUNDEEP
pythonrecursionpermutationbacktracking
bustrama
bustrama

Reputation: 61

Recursive permutation without loops or itertools

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

Upvotes: 0

Views: 615

Answers (3)

Alberto Cervantes
Alberto Cervantes

Reputation: 1

The functions func(n) and func1(list1,list2) will generate the permutations. Function func1 will multiply pairs n times. When n=1 , (a,b,c). Then when n=2, (a,b,c) x (a,b,c). When 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)

Displaying the output when func(2):

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

Upvotes: -1

Mulan
Mulan

Reputation: 135217

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

Upvotes: 1

Ajax1234
Ajax1234

Reputation: 71451

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

Upvotes: 2

Related Questions