Generating combinations algorithmically

Question

Suppose I have an n-high pyramid of numbers like:

    1
   5 8
  2 5 4
 8 9 3 1
2 8 3 7 2

How can I algorithmically walk through every possible path from the top of the pyramid to the bottom?

To better explain, let me represent the pyramid this way:

1 2 3 4 5
-----------
1         | a
5 8       | b
2 5 4     | c
8 9 3 1   | d
2 8 3 7 2 | e

For example:

        On the path | a b c d e (Path)
       -------------|------------------
Path 1:  1 5 2 8 2  | 1 1 1 1 1
Path 2:  1 5 2 8 8  | 1 1 1 1 2
Path 3:  1 5 2 9 8  | 1 1 1 2 2
Path 4:  1 5 2 9 3  | 1 1 1 2 3
...
Path m:  1 8 4 1 2  | 1 2 3 4 5

Where m is the total number of paths.

I understand that the problem can be reduced to simply generate all the possible paths denoted in the second column of the table, and I could come up fairly easily with an algorithm to generate those for a 5-high (or any other fixed high) pyramid, but I can't seem to come up with a general solution.

The algorithm cannot be recursive, for the simple reason that I've already solved the problem recursively and I'm interested in a non-recursive solution to get a complete view of the problem.

Answer 1

If you start at the top of the triangle there's only 2 choices to continue the path - left or right. If you chose left, then there's only 2 choices to continue the path - left or right. If you chose right, then there's only....

Let's encode the "left or right" decision at each level as 1 bit, where 0 = left and 1 = right. If there are 5 levels you can encode a path as 4 bits. If there are N levels you can encode a path as (N - 1) bits. The number of paths is 1 << (N - 1).

Now let's think about the bottom row. If you always choose "left" then it'd be path 0000b, which has no set bits, and you end up at the 0th number on the bottom row. If you always choose "right" then it'd be path 1111b, which has 4 set bits, and you end up at the 4th number on the bottom row. If you alternate (left, right, left, right) it'd be path 0101b, which has 2 set bits, and you end up at the 2nd number on the bottom row. If you alternate the opposite way (right, left, right, left) it'd be path 1010b, which has 2 set bits, and you end up at the 2nd number on the bottom row. The position of the number on the bottom row depends on how many set bits in the path.

Now think about the second to last row - it's the same as the last row, except you ignore the last bit! Just shift the path number right once, and count the number of set bits to determine the position of the number on the second to last row.

If you think about this; you probably don't even need to bother generating a table of paths in the first place - you could write a get_number(path, row) function and use that instead.

Answer 2

Maybe this:

Make a list t of left or right markers (0: left, 1: right) for all levels-1: So in your example t has 4 entries initially all set to zero (marking the first path) through your pyramid (tree).

so now you need to count through all left or right possibilities at each level (except level 0, which is the first node) we either go right or left :

Python:

pyr = [
        [1] ,     
        [5 ,8]     ,  
        [2,5, 4]   ,  
        [8, 9, 3, 1]   ,
        [2, 8,3, 7, 2] ]

pyrD = len(pyr)-1

t = [0]*pyrD

def getNodes(t):
      print("---------------")
      print("leftRightIndices: " , t)
      nodesIdx = [0]
      nodes = [ pyr[0][nodesIdx[0]] ]
      for idx,LorR in enumerate(t):
          nodesIdx.append( nodesIdx[idx]+LorR )
          nodes.append(pyr[idx+1][nodesIdx[idx+1]])

      print("nodes: " , nodes)
      print(nodes)


done = False
while not done:

    getNodes(t)

    for i in range(0,pyrD):
        carryOver = (t[i] + 1) > 1
        if not carryOver:
            t[i]+=1
            break;
        else:
            if i == pyrD-1:
                done = True
            t[i] = 0;

Which gives:

    ---------------
leftRightIndices:  [0, 0, 0, 0]
nodes:  [1, 5, 2, 8, 2]
---------------
leftRightIndices:  [1, 0, 0, 0]
nodes:  [1, 8, 5, 9, 8]
---------------
leftRightIndices:  [0, 1, 0, 0]
nodes:  [1, 5, 5, 9, 8]
---------------
leftRightIndices:  [1, 1, 0, 0]
nodes:  [1, 8, 4, 3, 3]
---------------
leftRightIndices:  [0, 0, 1, 0]
nodes:  [1, 5, 2, 9, 8]
---------------
leftRightIndices:  [1, 0, 1, 0]
nodes:  [1, 8, 5, 3, 3]
---------------
leftRightIndices:  [0, 1, 1, 0]
nodes:  [1, 5, 5, 3, 3]
---------------
leftRightIndices:  [1, 1, 1, 0]
nodes:  [1, 8, 4, 1, 7]
---------------
leftRightIndices:  [0, 0, 0, 1]
nodes:  [1, 5, 2, 8, 8]
---------------
leftRightIndices:  [1, 0, 0, 1]
nodes:  [1, 8, 5, 9, 3]
---------------
leftRightIndices:  [0, 1, 0, 1]
nodes:  [1, 5, 5, 9, 3]
---------------
leftRightIndices:  [1, 1, 0, 1]
nodes:  [1, 8, 4, 3, 7]
---------------
leftRightIndices:  [0, 0, 1, 1]
nodes:  [1, 5, 2, 9, 3]
---------------
leftRightIndices:  [1, 0, 1, 1]
nodes:  [1, 8, 5, 3, 7]
---------------
leftRightIndices:  [0, 1, 1, 1]
nodes:  [1, 5, 5, 3, 7]
---------------
leftRightIndices:  [1, 1, 1, 1]
nodes:  [1, 8, 4, 1, 2]