How to build all possible pairs from a string characters

user_13487355 0
Viewed 115

I want to, from a string, build pairs that contains all possible combinations of the string's characters.

# Exemple :
s = "ABCD"

# Desired result :
["A", "BCD"]
["B", "ACD"]
["C", "ABD"]
...
["AB", "CD"]
...
["BC", "AD"]
...
["ABC", "D"]
["ABD", "C"]
["ACD", "B"]
["BCD", "A"]
combinations python split
4 Answers

One way is to produce combinations of indices rather than the elements themselves with increasing r: 1, 2, .., length - 1. Then we find the remaining indices after combination selects. itemgetter can get the values given the indices and we can gather them in a list as strings:

from itertools import combinations
from operator import itemgetter

# given string and range till its length
s = "ABCD"
rng = range(len(s))

result = []
# for each combination possibility r...
for r in range(1, len(s)):
    # get the indices from `rng`
    for inds in combinations(rng, r):
        # find `others` that are not `inds` in `rng`
        others = [ind for ind in rng if ind not in inds]

        # now index into the string with these indices to find pairs
        first = itemgetter(*inds)(s)
        second = itemgetter(*others)(s)

        # store the stringifed pair
        result.append(["".join(first), "".join(second)])

which gives

>>> result

[["A", "BCD"],
 ["B", "ACD"],
 ["C", "ABD"],
 ["D", "ABC"],
 ["AB", "CD"],
 ["AC", "BD"],
 ["AD", "BC"],
 ["BC", "AD"],
 ["BD", "AC"],
 ["CD", "AB"],
 ["ABC", "D"],
 ["ABD", "C"],
 ["ACD", "B"],
 ["BCD", "A"]]
user_93321870

You could use the binary representation of a number with n binary digits: A zero means the corresponding character should go to the left, and a one that it should go to the right:

def pairs(s):
    for mask in range(1, 2**len(s) - 1):
        pair = ["", ""]
        for i, ch in enumerate(s):
            pair[(mask >> i) & 1] += ch
        yield pair

Example use:

print(list(pairs("ABCD"))
user_54598390

Not sure if this meets your needs, but more_itertools.set_partitions might be a solution.

from more_itertools import set_partitions

iterable = 'abcd'

for part in set_partitions(iterable, k=2):
    print([''.join(p) for p in part])

Prints:

['a', 'bcd']
['ab', 'cd']
['b', 'acd']
['abc', 'd']
['bc', 'ad']
['ac', 'bd']
['c', 'abd']
user_358120

You can use a recursive generator function:

def pairs(d, c = []):
  if not d and len(c) == 2:
     yield c
  elif d:
     for i, a in enumerate(d):
       if not c or len(c) == 1:
          yield from pairs(d[:i]+d[i+1:], c+[a])
       if c:
          yield from pairs(d[:i]+d[i+1:], c[:-1]+[c[-1]+a])

print(list(pairs('ABCD')))

Output:

[['A', 'BCD'], ['A', 'BDC'], ['AB', 'CD'], ['ABC', 'D'], ['AB', 'DC'], ['ABD', 'C'], ['A', 'CBD'], ['A', 'CDB'], ['AC', 'BD'], ['ACB', 'D'], ['AC', 'DB'], ['ACD', 'B'], ['A', 'DBC'], ['A', 'DCB'], ['AD', 'BC'], ['ADB', 'C'], ['AD', 'CB'], ['ADC', 'B'], ['B', 'ACD'], ['B', 'ADC'], ['BA', 'CD'], ['BAC', 'D'], ['BA', 'DC'], ['BAD', 'C'], ['B', 'CAD'], ['B', 'CDA'], ['BC', 'AD'], ['BCA', 'D'], ['BC', 'DA'], ['BCD', 'A'], ['B', 'DAC'], ['B', 'DCA'], ['BD', 'AC'], ['BDA', 'C'], ['BD', 'CA'], ['BDC', 'A'], ['C', 'ABD'], ['C', 'ADB'], ['CA', 'BD'], ['CAB', 'D'], ['CA', 'DB'], ['CAD', 'B'], ['C', 'BAD'], ['C', 'BDA'], ['CB', 'AD'], ['CBA', 'D'], ['CB', 'DA'], ['CBD', 'A'], ['C', 'DAB'], ['C', 'DBA'], ['CD', 'AB'], ['CDA', 'B'], ['CD', 'BA'], ['CDB', 'A'], ['D', 'ABC'], ['D', 'ACB'], ['DA', 'BC'], ['DAB', 'C'], ['DA', 'CB'], ['DAC', 'B'], ['D', 'BAC'], ['D', 'BCA'], ['DB', 'AC'], ['DBA', 'C'], ['DB', 'CA'], ['DBC', 'A'], ['D', 'CAB'], ['D', 'CBA'], ['DC', 'AB'], ['DCA', 'B'], ['DC', 'BA'], ['DCB', 'A']]
user_73267380
Related