Creating string combinations (not permutations)

Question

I tried to implement the algorithm in "Programming Interviews Exposed" in Python, as shown below, but it doesn't seem to work (page 99 on the second edition):

The idea is to generate all combinations (rather than permutations) of the string, so if you type "wxyz" you will get "w, wx, wxy, wxyz, wxz, wy, wyz, wz ...." and t .d., if wz is displayed, then zw is invalid.

def doCombine(strng, out, length, level, start): for i in range(start, length): out.append(strng[i]) print out if (i < length - 1): doCombine(strng, out, length, level +1, i + 1) out = out[:-1] x = list() target = "wxyz" print doCombine(target, x, len(target), 0, 0) 

What could be wrong here? I get relatively garbage output.

Answer 1

In your current code, try changing the line out = out[:-1] to del out[-1] . Both of these lead to out deleting the last element, but in your current code, out reassigned instead of using the same list. This leads to the fact that the characters are never removed from the original list, which, obviously, will be quite useless for output.

After making this change, here is the conclusion:

 >>> print doCombine(target, x, len(target), 0, 0) ['w'] ['w', 'x'] ['w', 'x', 'y'] ['w', 'x', 'y', 'z'] ['w', 'x', 'z'] ['w', 'y'] ['w', 'y', 'z'] ['w', 'z'] ['x'] ['x', 'y'] ['x', 'y', 'z'] ['x', 'z'] ['y'] ['y', 'z'] ['z'] None 

Answer 2

See the combination function () from the itertools module.

Answer 3

I rewrote this function of the harvester using a recursive generator. The conclusion is an iterator.

 def combine(s): length = len(s) def gen(start, prepending=[]): #recursive generator if start == length-1: yield prepending + [s[start]] else: for i in range(start,length): current = prepending + [s[i]] #save the current list for reusing yield current for els in gen(i+1,current): yield els for v in gen(0): yield v s = "wxyz" for v in combine(s): print(v) 

It is not very easy to understand right away.

The same technique is used in the connection generator: Function for combining into a functional style .

In addition, I reorganized your function a bit, trying to understand how it works. I will put it here for those who may be interested in facilitating their understanding.

 def combine(s): out = [] length = len(s) def loc(start): for i in range(start, length): out.append(s[i]) print out if (i < length-1): loc(i+1) del out[-1] loc(0) 

---

I made some performance calculations.

Code that uses adding and removing from out (slightly modified source poster code to act as a generator) is slightly faster than the code presented in this answer (I think because I used prepending + [s[i]] on each iteration, which creates a new list in memory. Adding and removing in the same list is faster).

Details here: https://ideone.com/V3WIM

Answer 4

The string out.append(strng[i]) does not match the described algorithm. You do not want to add, you want to specify [level] = strng [i]