CODEWITHSUNDEEP
javaalgorithmdata-structures
Mike M
Mike M

Reputation: 212

Calculate all possible combinations

Preface

Consider a list, array or string of 12 elements, of an irrelevant value (lets say E). Each element can be linked to, at most, one other adjacent element, or if it is the last element of the list, it can be linked to the first element.

Examples of valid lists, where dashes indicate links, and "E" represents an element.

E E E E E E E E E E E E 
E E-E E-E E E E-E E-E E
E E E-E E E-E E-E E E E-

An example of an invalid list.

E-E-E E E E E-E E E E E-

Question

I want to calculate the total number of unique lists, and print them.

To approach this problem, what might be the best way to represent the data?

Would it be best to implement a data structure specific to this problem?

I am looking to implement this in Java, but if you believe that a different language is better suited, I am open to suggestions.

Why

This is NOT a homework question.

The idea is to find every rhythmic pattern in a bar of 12/8 consisting of only single and double groupings of eighth notes, of which can be tied across a barline.

Upvotes: 6

Views: 625

Answers (3)

daniel gratzer
daniel gratzer

Reputation: 53911

Calculating the number of possibilities here actually has an incredibly neat solution (in my opinion).

Notice that for n notes, the number of possible connections ( C(n) ) if the first note is connected to the second is C(n-2). Otherwise it is C(n-1). This means that

C(n) = C(n-1) + C(n-2)
C(1) = 3 //Either the first and second are connected, 
         //neither are connected, or the end is connected.
C(0) = 2 //Either the end is connected or it isn't

Note: If the last note in a single note example can be connected "to itself" G(0) is 1 Otherwise, it is 0. In addition I am unclear whether E-E and E E- are separate, if they aren't then, C(1) is 2 not 3. Note these only apply for sequences of 0 or 1 on their own you'd have to have an if statement outside of the actual function C(n) to return 1 instead of 2. Otherwise it screws up the whole recurrence. A bit messy, but that's the nature of real world data in algorithms

This means you've basically got a variant on the fibonacci series! Cool right?

Data Representation

I would have a list of n booleans. An array would work fine. If 2 notes are connected, then that entry in the array should be true. I would have index 0 be the connection be the first and second notes, and index n-1 be whether or not the last note is connected to anything.

Permutation Generation

The way in which we calculate the total number of possibilities lends itself nicely to a generation method (G(n)). For n we need to tack on E-E to G(n-2) and E to G(n-1).

At the base of this recurrence we have:

G(0) = {E, E-} 
G(1) = {E-E, E E, E E-}

Upvotes: 4

Mihai Toader
Mihai Toader

Reputation: 12253

I think the total number of variants is 466.

One can compute the number as follows:

If we assume that a E-E link is marked as a Y then for example the total number of arrangement s in which only two E's are linked out of 12 is equal to the number of arrangements with repetitions of 2 items when the first is taken to be repeated 10 times and the second is taken to be repeated only one time. Basically this amounts to the following list: 

Y E E E E E E E E E E 
E Y E E E E E E E E E
E E Y E E E E E E E E
..
E E E E E E E E E E Y

This is basically the same as computing multinomial(10, 1) which is 11 ( http://www.wolframalpha.com/input/?i=multinomial%2810%2C+1%29 )

the total number is the following sum: 

multinomial(12) + // there is no E-E link at all 
multinomial(12 - 2, 1) + // only one E-E link 
multinomial(12 - 4, 2) + // two E-E links
...
multinomial(12 - 12, 6)  // 6 E-E links

this is 233 ( http://www.wolframalpha.com/input/?i=multinomial%2812%29+%2B+multinomial%2810%2C+1%29+%2B+multinomial%288%2C+2%29+%2B+multinomial%286%2C+3%29+%2B+multinomial%284%2C+4%29+%2B+multinomial%282%2C+5%29+%2B+multinomial%286%29 )

normally i would just multiply this by 2 to account for the end link possibility but this can actually create a chain of three E-E-E in some cases which will break your problem.

On the other side there are available algorithms to generate all the multinomial combinations for some parameters and since all of them are like 200 it's easy to generate all and just check which ones can be extended with the circular link at then end.

Upvotes: 0

Michael
Michael

Reputation: 637

If you let the inter-element spaces be your main data, then you have 12 "spaces" (the last one is the one after the end that ties to the first one).

Each "space" can either be blank or have a link. So you could represent it as 0 or 1. So there are at most 2^12 possibilities. That's a fairly small number (4096), so you could just generate all of them, then weed out the ones with adjacent 1s.

Upvotes: 0

Related Questions