Combinatorics challenge solved it Python

Question

The easiest way to explain this problem is to show these two test cases:

assert solution('ABC') == ['A', 'B', 'C', 'AB', 'AC', 'BC', 'ABC']
assert solution('ABCD') ==  ['A', 'B', 'C', 'D', 'AB', 'AC', 'AD', 'BC', 'BD', 'CD', 'ABC', 'ABD', 'ACD', 'BCD', 'ABCD']

my solution is below:

def subsolution(lst, length):
    return [lst + [x] for x in·
            range(lst[-1]+1, length)]

def solution(symbols):
    length = len(symbols)
    result = [[[x] for x in range(length)]]
    while True:
        subres = []
        for x in result[-1]:
            subres.extend(subsolution(x, length))
        if not subres:
            break
        result.append(subres)
    result = [ item for sublist in result
        for item in sublist
    ]
    result = [
        ''.join(symbols[s] for s in el)
        for el in result
    ]
    return result

Answer 1

Style

We all have our own 'what is the best' style. However even if you do something that others don't agree with, if you're consistent about it then that's all that matters.

From here you have some inconsistencies in your code.

• Indent style. You don't have a fixed style, and you've mixed two styles together to make something I think both sides can agree is not right.

  • With opening delimiter:

    return [lst + [x] for x in·
            range(lst[-1]+1, length)]
    

  • Hanging indent:

    result = [
        ''.join(symbols[s] for s in el)
        for el in result
    ]
    

  • Both:

    result = [ item for sublist in result
        for item in sublist
    ]
    

• You're not consistent in your newlines in comprehensions.

  • Item and for _ in on first line:

    return [lst + [x] for x in·
            range(lst[-1]+1, length)]
    

  • Item and entire for _ in ... on first line:

    result = [ item for sublist in result
        for item in sublist
    ]
    

  • Item on first line:

    result = [
        ''.join(symbols[s] for s in el)
        for el in result
    ]
    

We can fix these by just having a consistent style.

return [
    lst + [x]
    for x in range(lst[-1]+1, length)
]

result = [
    item
    for sublist in result
    for item in sublist
]

result = [
    ''.join(symbols[s] for s in el)
    for el in result
]

Improvements

• Your last two comprehensions that build two lists are wasteful when you can just merge the comprehensions together. This will also improve readability.

  return [
      ''.join(symbols[s] for s in item)
      for sublist in result
      for item in sublist
  ]
  

• Your code is not very readable. I can't tell that you're effectively calling itertools.combinations len(symbols) times.

  Whilst combinatorics are not very pleasant to read, your code doesn't show the most basic part clearly.

  def solution(symbols):
      for i in range(1, 1 + len(symbols)):
          yield from itertools.combinations(symbols, i)
  

Overall

You should get a consistent style and your code has some improvements to be made. However your code is pretty good on the combinations front. The range aspect is smart, maybe too smart, but if you used a docstring to explain the input and output then the implementation details can be guessed at fairly easily from your code.

Answer 2

My recursive solution:

Logic: You are taking a string. You are appending three types of strings to the ALL_VALUES list.

1. 0th indexed character pair with all other characters for each string in the recursion stack.
2. Each string that is in recursion stack.
3. List of all characters individually.

Now you are adding the string characters, all characters pair with 0th positioned character and rest all removing the leftmost character and doing it recursively.

ALL_VALUES = []


def find_all_subsets(string):
    if string:
        ALL_VALUES.extend(
            [string] + ([string[0] + character for character in string[1:]])
        )
        find_all_subsets(string[1:])


find_all_subsets(string)
print(set(ALL_VALUES + list(string)))

Outputs:

string = "ABCD"  # Output {'A', 'B', 'CD', 'D', 'BD', 'C', 'BC', 'AD', 'AB', 'AC'}

string = "ABC"  # Output = {'AC', 'C', 'AB', 'A', 'BC', 'B'}