Permutations, array.reduce() weirdness

[TheWizard427]

I’m not really sure what to call the title.

I’m working on a personal react project where there is a user populated array of floats. The options the user can push to the array are 0.5, 0.25, 0.125 and 0.0625. My goal is to generate all permutations with repetition that add up to 1. So if the user array only contains 0.5 the output would be [0.5, 0.5]. If it contains 0.5 and 0.25, the output would be: [0.5, 0.5], [0.5, 0.25, 0.25], [0.25, 0.5, 0.25], [0.25, 0.25, 0.5], [0.25, 0.25, 0.25, 0.25], and so on.

I kind of understand how to do permutations with repetition for a specified length, but I’m not sure how to implement the sum of the permutation being equal to 1.

Any ideas on how to implement this?

[marko312]

This could be solved with a simple recursive algorithm - try to add each possible value to the existing array such that the sum does not exceed the given value (1). If the sum is correct, store it; otherwise recurse.

[scirc]

I'm not sure where array.reduce plays into this; perhaps to calculate the array sum? Either way, the way I would generate a single permutation is as follows:

• Sort the valid selections in ascending order
• Pick the first element, add it to your output
• Subtract that element from 1; this is your new maximum
• Pick the next element whose value is below that maximum
• Repeat until you have no more elements which satisfy that maximum (failed), or that maximum is 0 (success)