Given N elements, divided into at most N groups, which are then labeled 1 thru N, move all of the elements into the group labeled 1. By moving 1 to all of the elements, in group i to i-1. This means that no elements from group 1 may be moved, although it will always have at least 1 marble.
A key thing to note is that once a group is "empty", it is removed from the list of groups. That is, a elements will never be moved into an empty group.
Edit #2: I should have clarified that I have an algorithm that determines which exactly elements will be moved. Which I'm thinking is enough to bring it down from exponential to polynomial.
Here are examples:
Example from worst case of N = 5 and groups = [1,1,1,1,1] move 1 from 4, result: [1,1,2,1] move 2 from 3, result: [1,3,1] move 3 from 2, result: [4,1] move 1 from 2, result: [5], finished All ways for N = 3 (total = 3): [1,1,1] -> [2,1] -> [3] [1,1,1] -> [1,2] -> [3] [1,1,1] -> [1,2] -> [2,1] -> [3] All ways for N = 4: [1,1,1,1] -> [2,1,1] -> [3,1] -> [4] [1,1,1,1] -> [2,1,1] -> [2,2] -> [4] [1,1,1,1] -> [2,1,1] -> [2,2] -> [3,1] -> [4] [1,1,1,1] -> [1,2,1] -> [3,1] -> [4] [1,1,1,1] -> [1,2,1] -> [2,1,1] -> [3,1] -> [4] [1,1,1,1] -> [1,2,1] -> [2,1,1] -> [2,2] -> [4] [1,1,1,1] -> [1,2,1] -> [2,1,1] -> [2,2] -> [3,1] -> [4] [1,1,1,1] -> [1,2,1] -> [1,3] -> [4] [1,1,1,1] -> [1,2,1] -> [1,3] -> [2,2] -> [4] [1,1,1,1] -> [1,2,1] -> [1,3] -> [2,2] -> [3,1] -> [4] [1,1,1,1] -> [1,1,2] -> [2,2] -> [4] [1,1,1,1] -> [1,1,2] -> [2,2] -> [3,1] -> [4] [1,1,1,1] -> [1,1,2] -> [1,2,1] -> [3,1] -> [4] [1,1,1,1] -> [1,1,2] -> [1,2,1] -> [2,1,1] -> [3,1] -> [4] [1,1,1,1] -> [1,1,2] -> [1,2,1] -> [2,1,1] -> [2,2] -> [4] [1,1,1,1] -> [1,1,2] -> [1,2,1] -> [2,1,1] -> [2,2] -> [3,1] -> [4] [1,1,1,1] -> [1,1,2] -> [1,2,1] -> [1,3] -> [2,2] -> [4] [1,1,1,1] -> [1,1,2] -> [1,2,1] -> [1,3] -> [2,2] -> [3,1] -> [4] [1,1,1,1] -> [1,1,2] -> [1,2,1] -> [1,3] -> [3,1] -> [4] [1,1,1,1] -> [1,1,2] -> [1,2,1] -> [1,3] -> [4] [1,1,1,1] -> [1,1,2] -> [1,3] -> [3,1] -> [4] [1,1,1,1] -> [1,1,2] -> [1,3] -> [2,2] -> [4] [1,1,1,1] -> [1,1,2] -> [1,3] -> [2,2] -> [3,1] -> [4]
I'm trying to figure out if a brute force implementation of this, that tries all possible ways grows polynomially or exponentially in N.
I'm thinking it's polynomial, since the number of ways seems like it cannot exceed the sum of the squares from 1 to N. However, I can't say for sure that I didn't miss something.
I would appreciate independent confirmation of this, an equation showing exactly how the number of ways grows with N would be an ideal answer.
Edit: I've added all ways for N = 3 and N = 4. I'm thinking I got all of them for N = 4.
Edit #3: Replaced all instances of "marbles" with elements, which is easier to associate with being able to determine which ones to move. Also to clarify, when for example 5 elements are moved, which 5 doesn't matter, as for a given group of elements, the same 5 will always be picked.