I think I am trying to do something quite fundamental and quite simple. For this reason, I was sure Stack Overflow would already have a post regarding this task but I guess not? Maybe it is an inconsequential concept? Apologies if a post for this already exists. I couldn't find it.
Here is what I want to accomplish: Given a list length n and a maximum element value m, generate all of the permutations of the list with each element varying between 0 and m.
QUESTIONS: 1. Is there a way to do this recursively? 2. Is recursion optimal (in terms of computational resources, O time, etc.) for this concept or is iteration better? 3. Is there a better way (less complicated) to achieve this using iteration (see my code below)?
more information found below
I have edited my code and the two examples to produce and exhibit complete solutions
Here are two examples:
Example 1: n = 3, m = 2 Output:
[0, 0, 0]
[0, 0, 1]
[0, 0, 2]
[0, 1, 0]
[0, 1, 1]
[0, 1, 2]
[0, 2, 0]
[0, 2, 1]
[0, 2, 2]
[1, 0, 0]
[1, 0, 1]
[1, 0, 2]
[1, 1, 0]
[1, 1, 1]
[1, 1, 2]
[1, 2, 0]
[1, 2, 1]
[1, 2, 2]
[2, 0, 0]
[2, 0, 1]
[2, 0, 2]
[2, 1, 0]
[2, 1, 1]
[2, 1, 2]
[2, 2, 0]
[2, 2, 1]
[2, 2, 2]
Example 1: n = 2, m = 4 Output:
[0, 0]
[0, 1]
[0, 2]
[0, 3]
[0, 4]
[1, 0]
[1, 1]
[1, 2]
[1, 3]
[1, 4]
[2, 0]
[2, 1]
[2, 2]
[2, 3]
[2, 4]
[3, 0]
[3, 1]
[3, 2]
[3, 3]
[3, 4]
[4, 0]
[4, 1]
[4, 2]
[4, 3]
[4, 4]
My intuition tells me this can be done recursively but I can't think of how to do it (I'm a beginner programmer). Currently, I have a solution to achieve this iteratively:
def permute(curr_permute,max_num,reset_flgs,reset_ind):
'''
Increment Logic Structure
'''
perm_ind = 0
max_val_flgs = [0]*len(curr_permute)
for c_i in range(len(curr_permute)):
if ((curr_permute[c_i] == max_num) and (c_i < (len(curr_permute)-1))):
if ((reset_ind == c_i) and (reset_flgs[c_i] == 1)):
reset_ind += 1
reset_flgs[c_i] = 0
max_val_flgs[c_i] = 1
continue
else:
perm_ind += 1
max_val_flgs[c_i] = 1
elif (c_i == (len(curr_permute)-1)):
if (curr_permute[c_i] == max_num):
perm_ind = c_i
max_val_flgs[c_i] = 1
else:
perm_ind = c_i
elif (curr_permute[c_i] < max_num):
perm_ind += 1
'''
Reverse the lists
'''
max_val_flgs.reverse()
curr_permute.reverse()
reset_flgs.reverse()
'''
Reset Logic Structure
'''
for n_i in range(len(curr_permute)):
if (max_val_flgs[n_i] == 0):
break
elif ((max_val_flgs[n_i] == 1) and (reset_flgs[n_i] == 1)):
curr_permute[n_i] = 0
perm_ind += -1
'''
Reverse the lists
'''
curr_permute.reverse()
reset_flgs.reverse()
'''
Apply the permutation increment
'''
curr_permute[perm_ind] += 1
return(curr_permute,reset_flgs,reset_ind)
def Permutation_Generation():
n = 2
m = 4
curr_permute = [0]*n
reset_flgs = [1]*n
reset_ind = 0
All_Permutations = [list(curr_permute)]
while (sum(curr_permute) < (n*m)):
print(curr_permute)
[curr_permute,reset_flgs,reset_ind] = permute(curr_permute,m,reset_flgs,reset_ind)
All_Permutations.append(list(curr_permute))
print(curr_permute)
return(All_Permutations)
Apologies for the garbage code. Once I came up with a way to do it successfully, I didn't make much effort to clean it up or make it more efficient. My guess is this code is too complicated for the concept I am attempting to address.
I don't think your output with n and m are 3, 2, respectively, really make sense. After 6th row [0, 2, 0], shouldn't it be followed by [0, 2, 1] instead of [1, 0, 0]? Same also happened after 13th row.
Anyway here is an recursive alterantive:
n = 3
m = 2
def permutation(n, m):
if n <= 0:
yield []
else:
for i in range(m+1):
for j in permutation(n-1, m):
yield [i] + j
# or even shorter
def permutation(n, m):
return [[i] + j for i in range(m + 1) for j in permutation(n - 1, m)] if n > 0 else []
for i in permutation(n, m):
print(i)
Output:
[0, 0, 0], [0, 0, 1], [0, 0, 2], [0, 1, 0], [0, 1, 1], ..., [2, 1, 0], [2, 1, 1], [2, 1, 2], [2, 2, 0], [2, 2, 1], [2, 2, 2]]