Combinatoric question_问答_开发者_运维开发者技术经验分享

I've got what I think is a "enumerative combinatoric" question.

I need to choose 7 elements out of 15 with repetition and I'd like to know if there's an easy way to store all combination in an array and directly find the element I'm interested in.

Basically I'm building a big lookup table (containing a very expensive to compute value) and I'd like to know if I can access it using a simple formula (note that this is not homework, check my profile).

The开发者_StackOverflow number of combinations with repetition for 7 out of 15 is 116 280 (I double checked that it is correct).

Here's the code :

public static void main(String[] args) {
    final Random r = new Random( System.currentTimeMillis() );
    final List<String> ls = new ArrayList<String>();
    for (int i = 0; i < 15; i++) {
        for (int j = i; j < 15; j++) {
            for (int k = j; k < 15; k++) {
                for (int l = k; l < 15; l++) {
                    for (int m = l; m < 15; m++) {
                        for (int n = m; n < 15; n++) {
                            for (int o = n; o < 15; o++) {
                                ls.add( i + " " + j + " " + k + " " + l + " " + m + " " + n + " " + o + ": " + r.nextLong() );
                            }
                        }
                    }
                }
            }
        }
    }
    System.out.println( "We have " + ls.size() + " entries" );
    System.out.println( "Entry @ 5,7,2,10,11,8,3 is " + getEntryAt(5,7,2,10,11,8,3) );
}

private static String getEntryAt( int i, int j, int k, int l, int m, int n, int o ) {
    return "FILL ME"; // What goes here ?
}

In the above example I'm just putting a random value in the lookup array but this is basically it: I want to get, say, (5,7,2,10,11,8,3), can I "compute" easily it's location?

Note that the way I'm storing elements in the array has no importance: I can store them in the way that makes for the fastest "formula", if any.

If anyone knows what I'm talking about any help would be much welcome.

The simple way to break it down is to sum the counts as parts. (For my examples, I used 1-based index)

Let's say you're given (fewer digits, but same principle) the tuple ( 2, 3, 4 ). Its position is simply the sum of:

( 1, x, y ) - all the numbers that fit into this
( 2, 2, x )
( 2, 3, x ) - where x < 4

and you can figure this out iteratively.

Now, for D = 3 digits, and K items, you can draw out the pattern and see how it grows:

for each iteration, what you're doing is actually taking the previous groupings (include an empty grouping) and adding an additional number -- as in the triangular number sequence. You can even think of this recursively as you increase the first digit -- in the above example of D = 3, K = 3, you can re-map the symbols of the stuff that doesn't start with "1", and thus they do not contain any "1"s - D is still 3, but K is now 2:

K = 3 (ignoring 1's)

2 2 2
2 2 3

2 3 3

3 3 3

becomes:

This is how you would add to K. (For D = 3, notice that they are triangular numbers.)

How about adding a digit? Well, for K = 3, D = 3, you can imagine, given this:

and add a digit in front of them. You can add "1" in front of all of them. You can only add "2" in front of the "2" or higher, and "3" to the one with only "3"s. Now you can see the recursive structure.

For a simple example, to find the index of ( 2, 4, 4 ) with D = 3, K = 5:

index( 2, 4, 4 ) =
   # number of leading 1's, and re-index
   index( 3, 3 ) + count( D = 2, K = 5 ) =
   index( 3, 3 ) + 15 =
   # number of leading 1's and 2's, and re-index
   index( 1 ) + count( D = 1, K = 4 ) + count( D = 1, K = 3 ) + 15 =
   index( 1 ) + 4 + 3 + 15 = index( 1 ) + 22 = 
   22

So index( 2, 4, 4 ) = 22

Now the tricky part is figuring out count( D, K ), which is actually just C( K + D - 1, D ). You can now generalize this to your K = 15, D = 7.

// This is actually 0-based.
// Really should use an array or something to make it easy to generalize, 
// so I'm going to skip a lot of cut and paste
private static int getEntryAt( int i, int j, int k, int l, int m, int n, int o ) {
   int D = 7, K = 15;
   int total = 0;

   if ( i > 0 ) {
      for ( int index = 0; index < i; index++ ) {
         total += count( D, K - index );
      }
   }

   j -= i, k -= i, l -= i, m -= i, n -= i, o -= i;
   D--;
   K -= i;
   // repeat for j, k, ...

   return count;
}

long[,,,,,,] ls = new long[15, 15, 15, 15, 15, 15, 15];

and in your deeply nested for loops:

ls[i, j, k, l, m, n, o] = r.nextLong();

and for your get statements, it's as simple as:

return ls[i, j, k, l, m, n, o];

But for this, ls needs to be either passed as a parameter to the getter function or it needs to be global.

Build a tree of height 7. The root node has 15 children, named 1-15. Each child name corresponds to the selection of that number in the set. A node with number n has children with numbers m (n <= m <= 15) At the leaves of the tree (all 116 280 of them, all have depth 7) you link to the pre-computed solution for that combination.

Looking up the solution for a given set then requires you tracing the relevant path through the tree, which can be done in constant time.

Perhaps you could use combinatorial number system to solve your problem?

Seems like you want a Map<Multiset,T> where T is the type of your expensive-to-compute value(s). A HashMap<Multiset,T> would use an array internally, so I guess that is a valid answer.

The point of making the key a Multiset is that the equals() method on the multiset should consider two multisets to be equal if they contain the same numbers of each element, disregarding ordering. (By the way, the JDK doesn't have a Multiset class, but you can find third-party Multiset classes.)