How to get all combinations with no repeats?

Question

So, I started off with this array:

array = ['A', 'B', 'C', 'D', 'E', 'F']

And I played around for a little while before getting python to print each unique, non-repeating combination, like so:

AB,
AC,
AD,
AE,
AF,
BC,
BD,
BE,
BF,
CD,
CE,
CF,
DE,
DF,
EF,

But now, I'd like to take all of these into a new array:

array2 = ['AB', 'AC', 'AD'...., 'EF']

And print all 3-element-long combinations, not including rearrangements, that have no repeats.

What I mean by 'no repeats':

AB, CD and EF is a 3-element long combination with no repeats, but AB, BD and EF is a 3-element-long combination with repeats, as 'B' appears in both 'AB' and 'BD'.

What I mean by 'not including rearrangements':

AB, CD, EF would be the same as BA, DC, FE, because all of the 2-letter elements are the same (BA is AB rearranged, DC is CD rearranged, and FE is EF rearranged). So ideally it'd print something like:

AB CD EF,
AB CE DF,
AB CF DE,
AC BD EF,
AC BE DF,
AC BF DE,
AD BC EF,
AD BE CF,
AD BF CE,
AE BC DF,
AE BD CF,
AE BF CD,
AF BC DE,
AF BD CE,
AF BE CD,

I believe those are all the combinations where no 2-letter element is repeated.

How would I go about printing this? Thanks!

So you want to keep the first position, i.e. `A`, fixed and permutate the remaining positions? Or should `BA CD EF` also be valid? — eol, Nov 19 '17 at 19:13
What is the difference with respect to all combinations (with permutations) of 6 elements? — Roberto Trani, Nov 19 '17 at 19:17
What code did you use to create that list of 2-item combinations? — PM 2Ring, Nov 19 '17 at 19:20
I would like to point out, that there is [`itertools.combinations`](https://docs.python.org/2/library/itertools.html#itertools.combinations) to get each unique, non-repeating combination. — C0DY, Nov 19 '17 at 19:43
The selected duplicate target shows how to use `itertools.combinations`, but that by itself is _not_ sufficient to produce the combinations that the OP wants. — PM 2Ring, Nov 19 '17 at 20:34
@martineau How is this a duplicate of that question? The problems in the 2 question may be somewhat related, but still totally different. — user2390182, Nov 19 '17 at 21:28

user2390182 · Answer 1 · 2017-11-19T21:26:21.923

3

Generator based recursive approach (without any itertools):

def comb(s):
  if len(s) == 2:
    yield [s]
  for x in s[1:]:
    first = ''.join((s[0], x))
    rest = ''.join(c for c in s if c not in first)
    for com in comb(rest):
      yield [first] + com

>>> list(comb('ABCDEF'))
[['AB', 'CD', 'EF'],
 ['AB', 'CE', 'DF'],
 ['AB', 'CF', 'DE'],
 ['AC', 'BD', 'EF'],
 ['AC', 'BE', 'DF'],
 ['AC', 'BF', 'DE'],
 ['AD', 'BC', 'EF'],
 ['AD', 'BE', 'CF'],
 ['AD', 'BF', 'CE'],
 ['AE', 'BC', 'DF'],
 ['AE', 'BD', 'CF'],
 ['AE', 'BF', 'CD'],
 ['AF', 'BC', 'DE'],
 ['AF', 'BD', 'CE'],
 ['AF', 'BE', 'CD']]

This takes the first element, pairs it with each of the other elements, and combines the resulting pair with every exhaustive pair list that can be made from the remaining elements. The base case is when there are only two elements.

Note: The assembling of rest presupposes that there are no repetitions in the initial string/sequence.

edited Nov 19 '17 at 21:26

answered Nov 19 '17 at 19:21

user2390182

72,016
6
67
89

I do like a recursive generator. ;) – PM 2Ring Nov 19 '17 at 19:27
See my answer for a speed comparison between your algorithm and a brute-force `itertools.combinations` solution. I'm sure you _won't_ be surprised. :) – PM 2Ring Nov 19 '17 at 20:01
Do you see there any chance to get all combinations with about for example 100 unique variables? Perhaps by dividing the 100 variables into blocks of 10 and then recombining them again? – Nils Jan 11 '21 at 17:18

PM 2Ring · Answer 2 · 2017-11-19T20:29:50.047

Here's a brute-force non-recursive version using itertools. It generates the pairs, and then makes all the combinations from those pairs, using sets to eliminate combinations that repeat any letters. It's much less efficient than schwobaseggl's generator, but it's still reasonably fast for small strings because combinations is very fast.

from itertools import combinations

def pairs(s):
    n = len(s)
    numgroups = n // 2
    for v in combinations(map(''.join, combinations(s, 2)), numgroups):
        if len(set(i for u in v for i in u)) == n:
            yield v

for t in pairs('ABCDEF'):
    print(t)

output

('AB', 'CD', 'EF')
('AB', 'CE', 'DF')
('AB', 'CF', 'DE')
('AC', 'BD', 'EF')
('AC', 'BE', 'DF')
('AC', 'BF', 'DE')
('AD', 'BC', 'EF')
('AD', 'BE', 'CF')
('AD', 'BF', 'CE')
('AE', 'BC', 'DF')
('AE', 'BD', 'CF')
('AE', 'BF', 'CD')
('AF', 'BC', 'DE')
('AF', 'BD', 'CE')
('AF', 'BE', 'CD')

On my 2GHz machine it takes around 13 seconds to print the 945 results for pairs('ABCDEFGHIJ'). In comparison, schwobaseggl's comb only takes 0.193 seconds. :)

Here's a smarter itertools version. This one still does more work than is necessary, but it's only about twice as slow as schwobaseggl's comb generator. We first produce combinations of half the size of the original string, and use set.difference to produce the complementary combination. We then permute that combination to combine it with the original combination.

from itertools import combinations, permutations

def pairs(s):
    a = set(s)
    for u in combinations(s, len(s) // 2):
        b = tuple(sorted(a.difference(u)))
        if b < u:
            break
        for v in permutations(b):
            c = [*zip(u, v)]
            if all(i<j for i, j in c):
                yield [*map(''.join, c)]

LOL, that last attempt looks like a a virtuoso explosion at the keyword and function factory! Have a rate for that :D — user2390182, Nov 19 '17 at 21:13
@schwobaseggl Thanks. It's hard trying to come up with algorithms for this that aren't simply disguised versions of yours. :) — PM 2Ring, Nov 19 '17 at 21:18
Yeah, this is quite a nice academic exercise... and not at all a duplicate of the marked question. I could revel in those for ages, too. — user2390182, Nov 19 '17 at 21:22

score 1 · Answer 3 · answered Nov 19 '17 at 23:22

A faster variation on PM 2Ring's code:

from itertools import combinations
array = ['A', 'B', 'C', 'D', 'E', 'F']
n = len(array)
numgroups = n // 2

array2 = map(''.join, combinations(array,2))
result = (' '.join(com) for com in combinations(array2,numgroups) if len(set(''.join(com)))==n)
for res in result:
    print res

How to get all combinations with no repeats?

3 Answers3