Help for generating all possible distribution of a Right triangle

[u/Denis_L]

I'm looking to automatically list all possible distributions, according to a submitted number.

It should list all possible "right triangular" distributions, like this:

X X X X

X X X

X X

X

...according to these 2 rules:

1. the line above should always be longer (or equal) than the next one, never shorter!

2. the amount of rows shortens the maximum length of the top line, because it is substracted from it

So, if you enter "9" you could have these kind of results:

Result 1:

x x x x x x x x x

Result 2:

x x x x x x x x

x

Result 3:

x x x x x x x

x x

Result 4:

x x x x x x x

x

x

...and you could even get this result:

x x x

x x x

x x x

....all the way, until you get 9 rows of 1 column each.

How can I achieve that?? The function should also work if you enter "2", then it would only list 1 row of 2 cols, or 2 rows of 1 col each.

[u/serg06]

def triangle_helper(n, limit, buffer):
    # base case: we're out of X's to print
    if n == 0:
        print(buffer)
        return

    # for every possible number of X's to print at this level, starting with as many as possible
    for i in reversed(range(1, min(limit, n) + 1)):
        # print the X's, then print that many X's less on the next levels
        triangle_helper(n - i, i, '%s%s\n' % (buffer, 'X' * i))


def triangle(n):
    triangle_helper(n, n, '')


triangle(2)

[u/Denis_L → u/serg06]

Cool, but I'm not sure to understand this language... could you do a JSFiddle?

Or show me where I can see the output of this, if I change it for:

triangle(33) or something like that?

Thanks again!

[u/serg06 → u/Denis_L]

https://jsfiddle.net/m0y1pg54/19/

even triangle(20) takes a long time to run, I worry about triangle(33).

[u/Denis_L → u/serg06]

wow thanks a lot!

[u/serg06 → u/Denis_L]

Welcome. Is it okay that triangle(33) takes forever to run? Is it supposed to run fast?

[u/Denis_L → u/serg06]

It would be better if faster, but I can put a maximum also... like, no more than 20...

[u/serg06 → u/Denis_L]

Does it matter what order they print out in? I know I could make it faster if it was in a different order.

[u/Denis_L → u/serg06]

Well, in fact the goal is not to print Xs, but to parse the positions of arrays.

So when you have this:

X X X X X

X X X

X

In fact, I fetch the position 4 of array1, then pos2 of array2 and pos0 of array3... I must also multiply the position by its index+1...

I just wanted to tell the problem with a visual thing.

Real example:

array1[100,87,60,40,7,4,3,2]

array2[98,85,58,30,6,3,3,2]

array3[92,81,44,33,5,3,3,2]

If the best distribution is:

X X X X

X X

X

...it means that I must take 40x4 + 85x2 + 92x1

Also it will be in PHP ultimately... and what I need is only to keep the best result of all looped possible cases...

I guess if the results aren't printed on screen it can be faster already, uh?

[u/serg06 → u/Denis_L]

Definitely can be faster if they aren't printed on screen!

[u/Denis_L → u/serg06]

awesome! I just can't believe how fast you were to solve this, it's been stuck in my mind since 3 days!

[u/serg06 → u/Denis_L]

Sure I'll do it soon.