I'm hoping someone could point me in the right direction... recursions are really throwing me off right now.
I need to print all permutations of a list, with the conditions that they're all printed in lexicographical order and that it needs to work with repeating elements.
For example, for a list of 1, 1, 2, it needs to print:
112
112
121
121
211
211
But if the list is 2, 2, 1:
122
122
212
212
221
221
This makes no sense to me because the first time, I "flip" the first two numbers, and the second time I flip the last two numbers. The professor even specifically said to use backtracking and I have no clue how to do this in recursion.
Here's what I have so far (can't paste the code because it's homework, but in python-y pseudocode):
Code:
list.sort()
perm is len(list) in size
repeatNum = 2**(number of repeats in list)
def func(list, perm, repeatNum, count=0):
if count equals the original list length
print perm repeatNum times, and return
for i in range(len(list)):
if we're on a repeat
continue
perm[count] = list[i]
list.pop(i)
func(list, perm, repeatNum, count+1)
list.insert(i, perm[count])
count is the perm index so I can reuse the list. Then I just go over all the permutations with backtracking, but there's basically 2 layers of duct tape:
- skipping all the repeat permutations
- printing every permutation the amount of duplicates that would be if I did it "properly"
It works perfectly, sure, but there has to be a better solution out there, right?