7

k個のアイテムのランダムなサブリストYをXから選択する必要がある問題を考えてみましょう。n個のアイテムのリストで、YのアイテムはXと同じ順序で表示される必要があります。Yで選択されたアイテムは次のようである必要はありません。明確。1つの解決策はこれです：

for i = 1 to k
    A[i] = floor(rand * n) + 1
    Y[i] = X[A[i]]
sort Y according to the ordering of A

ただし、ソート操作のため、実行時間はO（k log k）です。これを削除するには、

high_index = n
for i = 1 to k
    index = floor(rand * high_index) + 1
    Y[k - i + 1] = X[index]
    high_index = index

ただし、これにより、インデックスが均一に選択されるため、返されるリストに明確なバイアスがかかります。2番目の解の指数が不均一に分布している場合、O（k）解が達成可能であるように感じます。これが当てはまるかどうか、そしてもしそうなら、限界指数が引き出される分布がどのような特性を持っているかを誰かが知っていますか？

4

6 に答える 6

1

偏りO(n+k)のない解決策は、些細な高レベルの擬似コードです。

  • サイズnの空のヒストグラムを作成します[すべての要素をゼロとして初期化]
  • 範囲内にk個の均一に分散された変数を入力します。（k回行うhistogram[inclusiveRand(1,n)]++）
  • ヒストグラムの要素を減らし、結果リストに要素を追加しながら、初期リスト[A]を繰り返します。

説明[編集]：

  • アイデアは、ランダムにk要素を選択nし、それぞれに均一に分布させ、そこからヒストグラムを作成することです。
  • このヒストグラムには、インデックスごとに、結果のリストに表示されるi回数が含まれるようになりました。A[i]Y
  • ここで、リストを順番に繰り返し、A各要素について、結果のリスト時間iに挿入します。A[i]Yhistogram[i]
  • これにより、要素を順番に挿入し、「戻らない」ため、順序を維持できます。
  • また、各i、j、K：P(histogram[i]=K) = P(histogram[j]=K)についてK、各要素が結果のリスト時間に表示される確率が同じであるため、偏りのない解が保証されますK。

順序統計量[X （i） ]を使用して実行できると思いますが、理解できません：\O(k)

于 2012-04-11T12:43:42.533 に答える
1

最初のアルゴリズムでは、[0、1）のk個の均一なランダムサンプルをソートされた順序で生成するだけで十分です。

X1、...、Xkをこれらのサンプルとします。Xk = xとすると、X1、...、Xk-1の条件付き分布は、ソートされた順序で[0、x）のk-1の均一なランダムサンプルであるため、Xkをサンプリングして再帰するだけで十分です。

Xk <xになる確率はどれくらいですか？[0、1）のk個の独立したサンプルのそれぞれはx未満でなければならないため、答え（Xkの累積分布関数）はx^kです。累積分布関数に従ってサンプリングするには、[0、1）の均一なランダムサンプルで累積分布関数を反転するだけですpow(random(), 1.0 / k)。

これが、私が実際に実装を検討する（予想される）O（k）アルゴリズムです。アイデアは、サンプルをk個のビンにダンプし、各ビンを並べ替えて、連結することです。テストされていないPythonを次に示します。

def samples(n, k):
    bins = [[] for i in range(k)]
    for i in range(k):
        x = randrange(n)
        bins[(x * k) // n].append(x)
    result = []
    for bin in bins:
        bin.sort()
        result.extend(bin)
    return result

なぜこれが期待どおりに効率的ですか？各ビンで挿入ソートを使用するとします（各ビンのサイズはO（1）と予想されます！）。O（k）である操作に加えて、基本的に衝突の数であるビンサイズの2乗の合計の数に比例して支払います。2つのサンプルが衝突する確率はせいぜい4/kのようなものであり、サンプルのペアがO（k ^ 2）あるため、予想される衝突の数はO（k）です。

O（k）の保証は高い確率でできるのではないかと強く思います。

于 2012-04-11T13:37:03.173 に答える
0

カウントソートを使用してYをソートし、kに関してソートを線形にすることができます。ただし、そのためには、長さnの追加の配列が1つ必要です。すでにそれを割り当てていると仮定すると、複雑さO（k）で、要求しているコードを何度も実行できます。

考え方はあなたが説明したとおりですが、サイズnの配列cntをもう1つ使用し、0に初期化されていると想定し、もう1つの「スタック」stは空であると想定します。

for i = 1 to k
    A[i] = floor(rand * n) + 1
    cnt[A[i]]+=1
    if cnt[A[i]] == 1  // Needed to be able to traverse the inserted elements faster
      st.push(A[i])

for elem in st
  for i = 0 to cnt[elem]
    Y.add(X[elem])

for elem in st
  cnt[elem] = 0

編集：oldboyが述べたように、私が投稿で述べていることは真実ではありません-私はまだstをソートする必要があります。これは、元の提案よりも少し良いかもしれませんが、あまり多くはありません。したがって、このアプローチは、kがnに匹敵する場合にのみ有効であり、トラフcntを線形に反復し、この方法でYを作成します。このようにstは必要ありません：

for i = 1 to k
    A[i] = floor(rand * n) + 1
    cnt[A[i]]+=1

for i = 1 to k
  for j = 0 to cnt[i]
    Y.add(X[i])
  cnt[i] =0
于 2012-04-11T12:48:15.613 に答える
0

Yの最初のインデックスの場合、Xのインデックスの分布は次のようになります。

P（x; n、k）=二項（n-x + k-2、k-1）/ノルム

ここで、binomialは二項係数の計算を示し、normは正規化係数であり、可能なサブリスト構成の総数に等しくなります。

norm = binomial（n + k-1、k）

したがって、k=5およびn=10の場合、次のようになります。

  • ノルム=2002
  • P（x = 0）= 0.357、P（x <= 0）= 0.357
  • P（x = 1）= 0.245、P（x <= 1）= 0.604
  • P（x = 2）= 0.165、P（x <= 2）= 0.769
  • P（x = 3）= 0.105、P（x <= 3）= 0.874
  • P（x = 4）= 0.063、P（x <= 4）= 0.937
  • ...（これはx = 10まで続けることができます）

この分布からYの最初のアイテムのXインデックスをサンプリングできます（x1と呼びます）。次に、Yの2番目のインデックスの分布は、後続のすべてのインデックスについて、P（x;（n-x1）、（k-1））などを使用して同じ方法でサンプリングできます。

私は今、この問題はO（k）では解決できないと感じています。これは、一般に、一定時間で記述された分布からサンプリングすることができないためです。k = 2の場合、2次方程式を使用して一定時間で解くことができます（確率関数は0.5（x ^ 2 + x）に単純化されるため）が、これをすべてのkに拡張する方法がわかりません（私の数学は'でも素晴らしいです）。

于 2012-04-13T09:35:40.783 に答える
0

元のリストXにはn個のアイテムがあります。結果のサブリストにすべてのアイテムが表示される場合と表示されないため、2 ** nの可能なサブリストがあります。各アイテムは、可能なサブリストの列挙にビットを追加します。このnビットのビットワードの列挙を表示できます。

k個のアイテムを含むサブリストのみが必要なので、正確にkビットが設定されたビットワードに関心があります。

実際のアルゴリズムでは、Xから最初の要素を選択（または選択しない）してから、選択したアイテムの累積数を考慮して、Xの右端のn-1サブストリングに再帰することができます。Xリストは順番に処理されるため、Yリストも順番に処理されます。

于 2012-04-13T10:44:05.293 に答える
0

元のリストXにはn個のアイテムがあります。すべてのアイテムがサブリストに表示されるかどうかにかかわらず、2 ** nの可能なサブリストがあります。各アイテムは、可能なサブリストの列挙にビットを追加します。このnビットのビットワードの列挙を表示できます。

k個のアイテムを含むサブリストのみが必要なので、正確にkビットが設定されたビットワードに関心があります。実際のアルゴリズムでは、Xから最初の要素を選択（または選択しない）してから、選択したアイテムの累積数を考慮して、Xの右端のn-1サブストリングに再帰することができます。Xリストは順番に処理されるため、Yリストも順番に処理されます。

#include <stdio.h>
#include <string.h>

unsigned pick_k_from_n(char target[], char src[], unsigned k, unsigned n, unsigned done);
unsigned pick_k_from_n(char target[], char src[]
                , unsigned k, unsigned n, unsigned done)
{
unsigned count=0;

if (k>n) return 0;

if (k==0) {
        target[done] = 0;
        puts(target);
        return 1;
        }
if (n > 0) {
        count += pick_k_from_n(target, src+1, k, n-1, done);

        target[done] = *src;
        count += pick_k_from_n(target, src+1, k-1, n-1, done+1);
        }

return count;
}

int main(int argc, char **argv) {

char result[20];
char *domain = "OmgWtf!";
unsigned cnt ,len, want;
want = 3;

switch (argc) {
default:
case 3:
        domain = argv[2];
case 2:
        sscanf(argv[1], "%u", &want);
case 1:
        break;
        }
len = strlen(domain);

cnt = pick_k_from_n(result, domain, want, len, 0);

fprintf(stderr, "Count=%u\n", cnt);

return 0;
}

再帰を削除することは、読者の練習問題として残されています。いくつかの出力：

plasser@pisbak:~/hiero/src$ ./a.out 3 ABBA
BBA
ABA
ABA
ABB
Count=4
plasser@pisbak:~/hiero/src$
于 2012-04-13T11:15:47.983 に答える