Algorithm for finding all combinations of k elements from the stack n "randomly"
I have a problem similar to the one described here:
Algorithm for returning 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 greatly from what was done earlier. For example, if I were to draw a subset of 3 elements from a set of 8, the following algorithm would not be useful to me, since each subset is very similar to the previous one:
11100000, 11010000, 10110000, 01110000, ...
I'm looking for an algorithm that selects subsets in a more "random" way, i.e. where most of the elements in one subset are not reused in the following:
11100000, 00010011, 00101100, ...
Does anyone know of such an algorithm?
I hope my question got me started and someone can help me =)
Yours faithfully,
Christian
How do I first create all possible combinations of k out of n and then rearrange them with a random function.
If you have the result in a vector, loop through the vector: for each element, let it swap with the element at an arbitrary position.
This of course gets slow for large k and n.
a source to share
This is no coincidence, but depending on your needs, it might suit you.
- Calculate the number of possible combinations. Name them N.
- Calculate a large number that is coprime in N. Let's call it P.
- Order combinations and give them numbers from 1 to N. Call them C 1 on C N
- Iterating for combinations of output. The first will be V P mod N, the second - C 2 * P mod N, third - C 3 * P mod Netc. In essence, the output is understood as a module operator i= C i * P mod N. Mod.
If P is carefully chosen, you end up with seemingly random combinations. Values close to 1 or N will give values that differ little. It is better to choose values close to, for example, N / 4 or N / 5. You can also randomly generate P for each iteration you need.
a source to share
As a follow-up to my comment on this answer , here is some code that allows you to determine the composition of a subset from its "index", in colex. Shamelessly stolen from my own assignments.
//////////////////////////////////////
// NChooseK
//
// computes n!
// --------
// k!(n-k)!
//
// using Pascal 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 at random.
The order of colex is such that its unlocking function does not need a set size from which to select items to work; the cardinality is assumed by NChooseK (set size, subset size).
a source to share
How about randomly picking k items. those. choose pth where p is random between 1 and n, then change the order on the left and choose qth where q is between 1 and n-1, etc.?
or maybe I misunderstood. Do you still want all the possibilities? in this case, you can always generate them first and then select random entries from your list.
By "casual gaze" I think you mean the lexicographically distant. does this apply to the combination i
vs. i-1
or i
compared to all the previous combinations?
If so, here are some tips:
-
since most combinators produce ordered output, there are two options:
- design or find a generator that somehow gives unordered output
- list and store enough / all combinations in tie'd / db array file
-
if you decide to go with door # 2, then you can just get randomly ordered combinations of random integers between 1 and # combinations
-
As a final check, compare the current and previous combinations using a measure of the difference / distance between combinations, for example. for unsigned
Bit::Vector
in Perl:$ vec1-> Lexicompare ($ vec2)> = $ MIN_LEX_DIST
-
You can look behind door # 1, because even with moderate values
n
,k
you can get a large array:
EDIT:
Just looked at your comment on AnnK ... maybe lexicompare can help you skip similar combinations?
a source to share
Depending on what you are trying to do, you can make something like playing cards. Save two lists: Source
- your source (unused); and the Used
second is the "already selected" list. When you randomly select k
items from Source
, you move them to the list Used
.
If there are items k
left over Source
when you need to select again, you select them all and swap the lists. If there are fewer items k
, you select j
items from Used
and add them to Source
to make k
items to Source
, then select all of them and replace the lists.
It's like picking cards k
from a deck. You are dropping them onto the used heap. 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. Moreover, it does not guarantee that all possible subsets will be selected before the old ones are repeated.
The good thing is that you don't have to worry about precalculating all subsets, and your memory requirements are linear with your data (2 n
-different lists).
a source to share