Find all possible varients of max pair of 2-CodePudding

Given a string of numbers like 123456, I want to find all the possibilities they can be paired in by 2 or by itself. For example, from the string 123456 I would like to get the following:

12 3 4 5 6, 12 34 5 6, 1 23 4 56, etc.

The nearest I was able to come to was this:

strr = list("123456")
x = list("123456")

for i in range(int(len(strr)/2)):
    newlist = []
    for j in range(i):
        newlist.append(x[j])
    newlist.append(x[i]   x[i 1])
    for j in range(len(x))[i 2:]:
        newlist.append(x[j])
    x = newlist.copy()
    b = x.copy()
    for f in range(len(b))[i:]:
        if f == i:
            print(b)
            continue
        b[f] = b[f - 1][1]   b[f]
        b[f - 1] = b[f - 1][0]
        print(b)

This code gives the output:

output

CodePudding user response：

It's easy to solve this problem with a recursive generator. This is similar to how you solve change-making problems, just here we have only two "coins", either two characters together, or one character at a time. The total change we're trying to make is the length of the input string. The fact that the characters are digits in a numeric string is irrelevant.

def singles_and_pairs(string):
    if len(string) <= 1:             # base case
        yield list(string)           # yield either [] or [string] and then quit
        return

    for result in singles_and_pairs(string[:-1]): # first recursion
        result.append(string[-1:])
        yield result

    for result in singles_and_pairs(string[:-2]): # second recursion
        result.append(string[-2:])
        yield result

If you plan on running this on large input strings, you might want to add memoization, since the recursive calls recalculate the same results quite often.

CodePudding user response：

Pheew, this one took me some time to get right, but it seems to finally work (edited for prettier ordering):

def max_2_partitions(my_string):
    if not my_string:
        return [[]]
    if len(my_string) == 1:
        return [[my_string]]
    ret = []
    for i in range(len(my_string)):
        for l in max_2_partitions(my_string[:i]   my_string[i   1:]):
            li = sorted([my_string[i]] l, key = lambda x: (len(x),x))
            if li not in ret:
                ret.append(li)
        for j in range(i 1,len(my_string)):
            for l in max_2_partitions(my_string[:i] my_string[i 1:j] my_string[j 1:]):
                li = sorted([my_string[i]   my_string[j]]   l, key = lambda x: (len(x),x))
                if li not in ret:
                    ret.append(li)
    return sorted(ret, key=lambda x: (-len(x),x))

Example:

print(max_2_partitions("1234"))
# [['1', '2', '3', '4'], ['1', '2', '34'], ['1', '3', '24'], ['1', '4', '23'], ['2', '3', '14'], ['2', '4', '13'], ['3', '4', '12'], ['12', '34'], ['13', '24'], ['14', '23']]

CodePudding user response：

12 lines of code, full permutations:

You can first create permutations of the string, and then add spacing:

from itertools import permutations

def solution(A):
    result = []
    def dfs(A,B):
        if not B:
            result.append(A)
        else:
            for i in range(1,min(2,len(B)) 1):
                dfs(A [B[:i]],B[i:])
    
    for x in permutations(A):
        dfs([],''.join(x))
    return result

print(f"{solution('123') = }")
# solution('123') = [['1', '2', '3'], ['1', '23'], ['12', '3'], ['1', '3', '2'], ['1', '32'], ['13', '2'], ['2', '1', '3'], ['2', '13'], ['21', '3'], ['2', '3', '1'], ['2', '31'], ['23', '1'], ['3', '1', '2'], ['3', '12'], ['31', '2'], ['3', '2', '1'], ['3', '21'], ['32', '1']]