Algorithm for finding all combinations of k elements from stack of n "randomly"

Question

Hello,

I have a problem resembling the one described here:

http://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n

I am looking for something similar that covers all possible combinations of k from n. However, I need a subset to vary a lot from the one drawn previously. For example, if I were to draw a subset of 3 elements from a set of 8, the following algorithm wouldn't be useful to me since every subset is very similar to the one previously drawn:

11100000, 11010000, 10110000, 01110000, ...

I am looking for an algorithm thats picks the subsets in a more "random" looking fashion, ie. where the majority of elements in one subset is not reused in the next:

11100000, 00010011, 00101100, ...

Does anyone know of such an algorithm?

I hope my question made sence and that someone can help me out =)

Kind regards,

Christian

Answer 1

How about randomly choosing the k elements. ie choose the pth where p is random between 1 and n, then reorder what's left and choose the qth where q is between 1 and n-1 etc?

or maybe i misunderstood. do you still want all possibilities? in that case you can always generate them first and then choose random entries from your list

Answer 2

How about first generating all possible combinations of k from n, and then rearranging them with help of a random function.

If you have the result in a vector, loop through the vector: for each element let it change place with the element at a random position.

This of course becomes slow for large k and n.

Answer 3

This is not really random, but depending on your needs it might suit you.

1. Calculate the number of possible combinations. Let's name them N.
2. Calculate a large number which is coprime to N. Let's name it P.
3. Order the combinations and give them numbers from 1 to N. Let's name them C₁ to C_N
4. Iterate for output combinations. The first one will be V_{P mod N}, the second one will be C_{2*P mod N}, the third one C_{3*P mod N}, etc. In essence, Output_i = C_{i*P mod N.} Mod is meant as the modulus operator.

If P is picked carefully, you will get seemingly random combinations. Values close to 1 or to N will produce values that differ little. Better pick values close to, say N/4 or N/5. You can also randomize the generation of P for every iteration that you need.

Answer 4

As a follow-up to my comment on this answer, here is some code that allows one to determine the composition of a subset from its "index", in colex order. Shamelessly stolen from my own assignments.

//////////////////////////////////////
// NChooseK
//
// computes    n!
//          --------
//          k!(n-k)!
//
// using Pascal's identity
// i.e. (n,k) = (n-1,k-1) + (n-1,k)
//
// easily optimizable by memoization
long long NChooseK(int n, int k)
{
    if(k >= 0 && k <= n && n >= 1)
    {
        if( k > n / 2)
            k = n - k;
        if(k == 0 || n == 0)
            return 1;
        else
            return NChooseK(n-1, k-1) + NChooseK(n-1, k);
    } 
    else
        return 0;
}

///////////////////////////////////////////////////////////////////////
// SubsetColexUnrank
//  The unranking works by finding each element
//  in turn, beginning with the biggest, leftmost one.
//  We just have to find, for each element, how many subsets there are
//  before the one beginning with the elements we have already found.
//
// It stores its results (indices of the elements present in the subset) into T, in ascending order.
void SubsetColexUnrank(long long r, int * T, int subsetSize)
{
    assert( subsetSize >= 1 );

    // For each element in the k-subset to be found
    for(int i = subsetSize; i >= 1; i--)
    {
        // T[i] cannot be less than i
        int x = i;

        // Find the smallest element such that, of all the k-subsets that contain it,
        // none has a rank that exceeds r.            
        while( NChooseK(x, i) <= r )
            x++;

        // update T with the newly found element
        T[i] = x;

        // if the subset we have to find is not the first one containing this element
        if(r > 0)
        {
            // finding the next element of our k-subset
            // is like finding the first one of the same subset
            // divided by {T[i]}
            r -= NChooseK(x - 1, i);
        }
    }
}

Random-in, random-out.

The colex order is such that its unranking function does not need the size of the set from which to pick the elements to work; the number of elements is assumed to be NChooseK(size of the set, size of the subset).

Answer 5

Depending on what you are trying to do, you could do something like playing cards. Keep two lists: Source is your source (unused) list; and Used the second is the "already-picked" list. As you randomly pick k items from Source, you move them to your Used list.

If there are k items left in Source when you need to pick again, you pick them all and swap the lists. If there are fewer than k items, you pick j items from Used and add them to Source to make k items in Source, then pick them all and swap the lists.

This is kind of like picking k cards from a deck. You discard them to the used pile. Once you reach the end or need more cards, you shuffle the old ones back into play.

This is just to make sure each set is definitely different from the previous subsets. Also, this will not really guarantee that all possible subsets are picked before old ones start being repeated.

The good is that you don't need to worry about pre-calculating all the subsets, and your memory requirements are linear with your data (2 n-sized lists).