Алгоритм случайного нахождения всех комбинаций из k элементов из стека из n

Как насчет того, чтобы сначала сгенерировать все возможные комбинации k из n, а затем переставить их с помощью случайной функции.

Если у вас есть результат в векторе, выполните цикл по вектору: пусть для каждого элемента он поменяется местами с элементом в случайной позиции.

Это, конечно, становится медленным для больших k и n.

Это не совсем случайно, но в зависимости от ваших потребностей это может вам подойти.

1. Подсчитайте количество возможных комбинаций. Назовем их Н.
2. Вычислите большое число, взаимно простое с N. Назовем его P.
3. Упорядочите комбинации и дайте им номера от 1 до N. Назовем их от C₁ до C_N
4. Итерация для выходных комбинаций. Первый будет V_{P mod N}, второй будет C_{2*P mod N}, третий C_{3*P mod N} sub> и т. д. По сути, Output_i = C_{i*P mod N.} Mod подразумевается как оператор модуля.

Если P выбрать тщательно, вы получите кажущиеся случайными комбинации. Значения, близкие к 1 или к N, будут давать мало отличающиеся значения. Лучше выбирать значения, близкие, скажем, к N/4 или N/5. Вы также можете рандомизировать генерацию P для каждой необходимой вам итерации.

В продолжение моего комментария к этот ответ, вот некоторый код, который позволяет определить состав подмножества по его "индексу" в порядке колекса. Бессовестно украденный из моих собственных заданий.

//////////////////////////////////////
// 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);
        }
    }
}

Случайный вход, случайный выход.

Порядок колекса таков, что его функция неранжирования не нуждается в размере набора, из которого выбираются элементы для работы; предполагается, что количество элементов равно NChooseK (размер набора, размер подмножества).

Как насчет случайного выбора k элементов. т.е. выбрать p-й, где p является случайным между 1 и n, затем переупорядочить то, что осталось и выбрать q-й, где q находится между 1 и n-1 и т.д.?

или может я неправильно понял. Вы все еще хотите все возможности? в этом случае вы всегда можете сначала сгенерировать их, а затем выбрать случайные записи из своего списка.

Под «случайным поиском», я думаю, вы имеете в виду лексикографически отдаленный. Это относится к комбинации i против i-1 или i против всех предыдущих комбинаций?

Если да, то вот несколько предложений:

• поскольку большинство комбинаторов дают упорядоченный вывод, есть два варианта:

  1. design or find a generator which somehow yields non-ordered output
  2. перечислить и сохранить достаточно/все комбинации в связанном файле массива/db

• если вы решите пойти с дверью № 2, то вы можете просто получить доступ к случайно упорядоченным комбинациям случайными целыми числами от 1 до # комбинаций.

• В качестве окончательной проверки сравните текущую и предыдущую комбинации, используя меру разницы/расстояния между комбинациями, например. для беззнакового Bit::Vector в Perl:

  $vec1->Lexicompare($vec2) >= $MIN_LEX_DIST

• Вы можете еще раз заглянуть за дверь №1, так как даже при умеренных значениях n и k можно получить большой массив:

РЕДАКТИРОВАТЬ:

Только что увидел ваш комментарий к AnnK ... может быть, лексическое сравнение все еще может помочь вам пропустить похожие комбинации?

В зависимости от того, что вы пытаетесь сделать, вы можете сделать что-то вроде игры в карты. Держите два списка: Source — ваш исходный (неиспользуемый) список; и Used второй - это "уже выбранный" список. Когда вы случайным образом выбираете k элементов из Source, вы перемещаете их в свой Used список.

Если в Source осталось k элементов, когда вам нужно снова выбрать, вы выбираете их все и меняете списки местами. Если элементов меньше k, вы выбираете j элементов из Used и добавляете их в Source, чтобы получить k элементов в Source, затем выбираете их все и меняете списки.

Это похоже на выбор k карт из колоды. Вы сбрасываете их в использованную стопку. Как только вы дойдете до конца или вам понадобится больше карт, вы снова вмешиваете старые в игру.

Это просто для того, чтобы убедиться, что каждый набор определенно отличается от предыдущих подмножеств. Кроме того, это не гарантирует, что все возможные подмножества будут выбраны до того, как начнут повторяться старые.

Хорошо то, что вам не нужно беспокоиться о предварительном вычислении всех подмножеств, а ваши требования к памяти линейны с вашими данными (2 списка размером n).