ALL permutations of a list with repetition but not doubles

Question

I have seen similar but not the same: here. I definitely want the permutations, not combinations, of all list elements. Mine is different because itertools permutation of a,b,c returns abc but not aba (soooo close). How can I get results like aba returned as well?

('a',)     <-excellent
('b',)     <-excellent
('c',)     <-excellent
('a', 'b') <-excellent
('a', 'c') <-excellent
('b', 'a') <-excellent
('b', 'c') <-excellent
('c', 'a') <-excellent
('c', 'b') <-excellent
('a', 'b', 'c') <-- I need a,b,a
('a', 'c', 'b') <-- I need a,c,a
('b', 'a', 'c') <-- I need b,a,b... you get the idea

Oh max length of permutations ("r" in the python.org itertools) is equal to len(list), and I don't want to include 'doubles' such as aab or abb ...or abba :P The list could be any length.

import itertools
from itertools import product
my_list = ["a","b","c"]
#print list(itertools.permutations(my_list, 1))
#print list(itertools.permutations(my_list, 2))
#print list(itertools.permutations(my_list, 3)) <-- this *ALMOST* works

I combined the above into a for loop

def all_combinations(varsxx):
    repeat = 1
    all_combinations_result = []
    for item in varsxx:
        if repeat <= len(varsxx):
            all_combinations_result.append(list(itertools.permutations(varsxx, repeat)))
        repeat += 1
    return all_combinations_result

For reference, when I did this on paper I got 21 results.

Also is there any merit in converting the list of strings into a list of numbers. My thought was that numbers would be easier to work with for the permutations tool. Strings might be 10 to 50 chars..ish.

You need to describe what you exactly want more precisely. – Reblochon Masque Oct 30 '17 at 05:19 — Reblochon Masque, Oct 30 '17 at 05:19

score 6 · Accepted Answer · answered Oct 30 '17 at 05:28

Even though you "definitely want the permutations", it sounds like you don't really want that, you actually want the Cartesian product of your sequence with itself from 1 to len(sequence) times, with results with neighbouring equal elements filtered out.

Something like:

In [16]: from itertools import product

In [17]: def has_doubles(x): return any(i==j for i,j in zip(x, x[1:]))

In [18]: seq = ["a","b","c"]

In [19]: [x for n in range(len(seq)) for x in product(seq, repeat=n+1) 
            if not has_doubles(x)]
Out[19]: 
[('a',),
 ('b',),
 ('c',),
 ('a', 'b'),
 ('a', 'c'),
 ('b', 'a'),
 ('b', 'c'),
 ('c', 'a'),
 ('c', 'b'),
 ('a', 'b', 'a'),
 ('a', 'b', 'c'),
 ('a', 'c', 'a'),
 ('a', 'c', 'b'),
 ('b', 'a', 'b'),
 ('b', 'a', 'c'),
 ('b', 'c', 'a'),
 ('b', 'c', 'b'),
 ('c', 'a', 'b'),
 ('c', 'a', 'c'),
 ('c', 'b', 'a'),
 ('c', 'b', 'c')]

In [20]: len(_)
Out[20]: 21

That is awesome, you nailed it in one! :) Code worked 1st time, the doubles have been removed, the "products" are all there, the count is correct, and it works on larger lists as well :) Nailed *everything* :) Many thanks ! — DaftVader, Oct 31 '17 at 09:56
Thank you again for your help on this. Can I ask your help again please? I need to YIELD the result instead but my attempts at modifying this are proving unfruitful. I need to 'step' over the results. IE get the result ('a',) and work with it. Then move on to ('b',) — DaftVader, Nov 11 '17 at 01:34

ALL permutations of a list with repetition but not doubles

1 Answers1

Linked