Print n-length combinations without repetitions using recursion

Question

Further to this problem: Print n-length combinations from char list using recursion

Now I have to implement the same algorithm with some another twist: without repetitions of some char.

Implement a function in Python which recieves as parameters list of characters and an integer n. The function has to print all the possible combinations in the length of n, where every character can be shown only one time.

So, as I am a beginner and bad in recursion, I don't succeed to think of an elegant solution to solve that.

I have thought to use the same code from the previous problem:

def print_sequences(char_list, n, _accum=[]):
  if len(_accum) == n:
    print(_accum)
  else:
    for c in char_list:
      print_sequences(char_list, n, _accum+[c])

And simply build a new function (return_without_repetition) that takes a list and goes over it, builds a new list without repetitions. Such that when I print the list I use the function:

if len(_accum) == n:
    print(return_without_repetition(_accum))

But it's very not effective and not elegant.

Maybe there is another way to solve it by defining new lists in the body of the recursion but I got lost concerning the scoping and the suitable places to define the lists...

Just to clarify, do you mean combinations (where order of the values do not matter - e.g. `[1, 2, 3, 4]` and `[1, 2, 4, 3]` are considered the same value) or permutations (where the example would be count as two values)? The accepted answer to your previous question gives you permutations. — tarheel, Dec 04 '18 at 21:42

tarheel · Accepted Answer · 2018-12-04T22:25:09.590

Modifying the logic in @Ajax1234's answer in the linked question to simply skip an iteration of the for loop if its going to repeat a value in the _accum list would look like this:

def print_sequences(char_list, n, _accum=[]):
    if len(_accum) == n:
        print(_accum)
    else:
        for c in char_list:
            if c in _accum:
                continue
            print_sequences(char_list, n, _accum+[c])

print_sequences([1, 2, 3, 4], 4)

According to this explanation of combinations and permutations we can calculate the expected number of results using 4!, which is 24. (The same linked page explains why 4⁴, or 256, is the expected number of results in the answer to your previous question)

The answer above will print out the following 24 result lists:

[1, 2, 3, 4]
[1, 2, 4, 3]
[1, 3, 2, 4]
[1, 3, 4, 2]
[1, 4, 2, 3]
[1, 4, 3, 2]
[2, 1, 3, 4]
[2, 1, 4, 3]
[2, 3, 1, 4]
[2, 3, 4, 1]
[2, 4, 1, 3]
[2, 4, 3, 1]
[3, 1, 2, 4]
[3, 1, 4, 2]
[3, 2, 1, 4]
[3, 2, 4, 1]
[3, 4, 1, 2]
[3, 4, 2, 1]
[4, 1, 2, 3]
[4, 1, 3, 2]
[4, 2, 1, 3]
[4, 2, 3, 1]
[4, 3, 1, 2]
[4, 3, 2, 1]

How do I show formally the running time of this function? For me, it looks like n^2 but how to show that formally? Thanks. — HelpMe, Dec 05 '18 at 10:00
In terms of the [tag:Big-O] notation of this process, I would say its somewhere between O(n!) and O(n^n) given that the final solution is equal to 4! and the total number iterations of the `for` loop (assuming there was no `continue` in there) would be 4^4 (256). That said, something like that might warrant its own question, if it is sufficiently unique from [existing questions like this](https://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it). — tarheel, Dec 05 '18 at 18:44

score 0 · Answer 2 · answered Jun 21 '19 at 01:09

This problem is actually all non-repeating permutations of size k. Here is an easy to read version of it:

def permutations(items, k):
   def f(path):
      if len(path) == k:
         print(path)
         return
      else:
         for item in items:
             if item not in path:
                 f(path + [item])
      f([])

Calling this function gives:

[1, 2, 3, 4]
[1, 2, 4, 3]
[1, 3, 2, 4]
[1, 3, 4, 2]
[1, 4, 2, 3]
[1, 4, 3, 2]
[2, 1, 3, 4]
[2, 1, 4, 3]
[2, 3, 1, 4]
[2, 3, 4, 1]
[2, 4, 1, 3]
[2, 4, 3, 1]
[3, 1, 2, 4]
[3, 1, 4, 2]
[3, 2, 1, 4]
[3, 2, 4, 1]
[3, 4, 1, 2]
[3, 4, 2, 1]
[4, 1, 2, 3]
[4, 1, 3, 2]
[4, 2, 1, 3]
[4, 2, 3, 1]
[4, 3, 1, 2]
[4, 3, 2, 1]

Print n-length combinations without repetitions using recursion

2 Answers2