1

ここで説明されている問題に似た問題があります。

n から k 個の要素のすべての組み合わせを返すアルゴリズム

nからkのすべての可能な組み合わせをカバーする同様のものを探しています。ただし、以前に描いたものとは大きく異なるサブセットが必要です。たとえば、8 つの要素のセットから 3 つの要素のサブセットを描画する場合、すべてのサブセットが以前に描画されたものと非常に似ているため、次のアルゴリズムは役に立ちません。

11100000、11010000、10110000、01110000、...

より「ランダム」に見える方法でサブセットを選択するアルゴリズムを探しています。1 つのサブセット内の要素の大部分は、次のサブセットでは再利用されません。

11100000、00010011、00101100、...

そのようなアルゴリズムを知っている人はいますか？

私の質問が理にかなっており、誰かが私を助けてくれることを願っています =)

敬具、

キリスト教徒

4

6 に答える 6

1

この回答に対する私のコメントのフォローアップとして、「インデックス」からサブセットの構成をコレックス順に決定できるようにするコードを次に示します。私自身の任務から恥知らずに盗まれました。

//////////////////////////////////////
// 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 (セットのサイズ、サブセットのサイズ) と見なされます。

于 2009-05-12T02:36:43.643 に答える
1

最初に n から k のすべての可能な組み合わせを生成し、次に乱数関数を使用してそれらを並べ替えてみませんか。

結果がベクトルにある場合は、ベクトルをループします。各要素について、ランダムな位置にある要素で場所を変更します。

もちろん、これは大きな k と n では遅くなります。

于 2009-05-11T10:16:12.173 に答える
0

k 個の要素をランダムに選択するのはどうですか。つまり、p が 1 から n の間でランダムな p 番目を選択し、残っているものを並べ替えて、q が 1 から n-1 の間である q 番目を選択します。

または多分私は誤解しました。あなたはまだすべての可能性を望んでいますか？その場合、常に最初にそれらを生成してから、リストからランダムなエントリを選択できます

于 2009-05-11T10:13:35.050 に答える
0

やろうとしていることに応じて、トランプのようなことをすることができます。2 つのリストSourceを保持します。ソース (未使用) リストです。2つUsed目は「選択済み」リストです。kからアイテムをランダムに選択Sourceすると、それらがリストに移動しますUsed。

再度選択する必要があるときにkアイテムが残っている場合は、それらをすべて選択してリストを交換します。Sourceアイテムが少ない場合は、からアイテムkを選択して に追加し、でアイテムを作成してから、すべてを選択してリストを入れ替えます。jUsedSourcekSource

kこれは、デッキからカードを選ぶようなものです。それらを使用済みパイルに捨てます。最後に到達するか、さらにカードが必要になったら、古いカードをシャッフルして場に戻します。

これは、各セットが以前のサブセットと明確に異なることを確認するためです。また、これは、古いサブセットが繰り返される前に、すべての可能なサブセットが選択されることを実際に保証するものではありません。

良い点は、すべてのサブセットを事前に計算することを心配する必要がなく、メモリ要件がデータに比例することです (2nサイズのリスト)。

于 2009-05-12T14:08:35.860 に答える
0

「ランダムに見える」とは、辞書編集的に離れていることを意味していると思います..これは、組み合わせivs. i-1、またはivs.以前のすべての組み合わせに適用されますか?

もしそうなら、ここにいくつかの提案があります：

  • ほとんどのコンビネータは順序付けされた出力を生成するため、2 つのオプションがあります。

    1. どういうわけか順序付けられていない出力を生成するジェネレーターを設計または見つける
    2. 結合された配列ファイル/データベースに十分な/すべての組み合わせを列挙して保存します

  • ドア #2 を使用することにした場合は、1 から組み合わせの数までのランダムな整数によって、ランダムに並べられた組み合わせにアクセスできます。

  • 最後のチェックとして、組み合わせ間の差異/距離の尺度を使用して、現在と以前の組み合わせを比較します。たとえばBit::Vector、Perl の unsigned の場合:

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

  • nとの値が中程度であってもk、大きな配列を取得できるため、ドア #1 の後ろをもう一度見てみるとよいでしょう。

C(n,k) = n!/(k!(nk)!)

編集：

AnnK へのコメントを見たところですが、lexicompare が同様の組み合わせをスキップするのに役立つかもしれません。

于 2009-05-11T11:39:34.643 に答える