-2

私がこの実用的な例を持っているとしましょう:

lover_bound = 10;
upper_bound = 180;
steps = 10;
NumeroCestelli = 8; 

livello = [lover_bound:steps:upper_bound];
L = length(livello);
n_c = ceil((factorial(L+NumeroCestelli-1))/(factorial(NumeroCestelli)*factorial(L-1)));

randIdxs = randi([1,L],n_c,NumeroCestelli);
PianoSperimentale = single(livello(randIdxs));

各行が一意であるn_c x NumeroCestelliマトリックス ( と呼ばれる)を実行する必要があります。PianoSperimentaleいかなる形式の順列も許可されていません。randi を使用すると、私が求めていることを実行できません。

[10 20 30 40 50 60 70 80] is equal to [80 70 60 50 40 30 20 10]

PianoSperimentale1081575x8マトリックスでなければなりません。以前はCombinator ) 関数を使用していましたが、行列が非常に大きい場合は非常に遅くなります。

[PianoSperimentale] = combinator(L,NumeroCestelli,'c','r');

for i=1:L
    PianoSperimentale(PianoSperimentale==i)=livello(i);
end

それで、同じマトリックスを実行する方法がありcombinatorますが、randi速度はありますか?

編集: 同じ番号を 2 回選択できるようにします ( NumberOfCombinations = (NumeroCestelli+L-1)!/(NumeroCestelli!(L-1)!)

提案された編集

18 要素のベクトルから任意の 8 つの数値を選択するときに得られる組み合わせの完全なセット (重複あり) を生成する必要があります。これはCombinator関数を使用して実行できますが、行列が非常に大きい場合は非常に遅くなります。これを生成するためのより高速な方法を提案できる人はいますか?

例:「4 のベクトルからのサンプル 3」を使用すると、次の結果が得られます。

1 1 1
1 1 2
1 1 3
1 1 4
1 2 2
1 2 3
1 2 4
1 3 3
1 3 4
1 4 4
2 2 2
2 2 3
2 2 4
2 3 3
2 3 4
2 4 4
3 3 3
3 3 4
3 4 4
4 4 4

18 個の要素からなるベクトルから 8 個を選択すると、(18+8-1)!/8!*(18-1)!可能な組み合わせの合計、つまり 8 個の値の 1081578 行が得られることがわかっています。これを行うための高速なアルゴリズムを見つけるのを手伝ってくれる人はいますか?

4

2 に答える 2

2

「歴史的な」理由から、古い回答を削除するのではなく、新しい回答を書いています（その質問の多くのやり取りは、質問を理解するために必要な前文であったため、この回答は理にかなっています）。TL;DR: 最後に完全なコード。

これは非常に難しい問題でしたが、理解できたと思います。重要な洞察は、結果行列の正しい要素数の式 が、(L+H-1)!/(H!(L-1)!)「 L + H - 1 から H を選択する」と問題の解決策の間に関係があることを強く示唆しているという事実でした。トリックはその関係を見つけることでした。最初に結果を書き出すことでこれを行いましたcombnk(5, 3)(このサイズでは、すべての組み合わせを手で書き出してパターンを探すことができます):

1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5

1 2 3これを(繰り返しを含む)の一意の組み合わせに変換するにはどうすればよいでしょうか? 数字が連続する 3 つのセットがあることに気付きました。

1 2 3
2 3 4
3 4 5

それは私が行の数の違いで何かをする必要があるという考えを私に与えました-どういうわけか、違いが1の場合、私は数を繰り返す必要がありました。この洞察はすぐに次のコードにつながりました。

L = 3; % pick three numbers
H = 3; % from three numbers: 1,2,3

a = combnk(1:L+H-1, L);  % generate all "combinations" of 1,2,3,4,5 without repeats

% the "magic" line: compress into "combinations with repeats"
b = cumsum([a(:,1)  diff(a,[],2) - 1],2);

上記の例では、次のようになります。

 1 1 1
 1 1 2
 1 1 3
 1 2 2
 1 2 3
 1 3 3
 2 2 2
 2 2 3
 2 3 3
 3 3 3

どうしてこうなりました？さて、diff（2次元に沿った）aの

 1 1
 1 2
 1 3
 2 1
 2 2
 3 1
 1 1
 1 2
 2 1
 1 1

そうdiff(a,[],2)-1)です

 0 0
 0 1
 0 2
 1 0
 1 1
 2 0
 0 0
 0 1
 1 0
 0 0

この式で、0は「最後の数字を繰り返す」、1は「1 を足す」、2「2 を足す」を意味します。cumsum(cumulative sum) 関数を使用して、組み合わせの最初の桁から開始することで、このすべての加算を行うことができます。という表現につながります。

b = cumsum([a(:, 1) diff(a, [], 2) - 1]);

最後のステップとして、これを使用しているインデックスに変換する必要があります。あなたの完全なコードは

L = 8;
H = 18;
a = combnk(1:L+H-1, L);
b = cumsum([a(:,1)  diff(a,[],2) - 1],2);
livello = 10:10:180;
PianoSperimentale = livello(b);

bサイズがで、値がの配列が作成されlivelloます。

これでうまくいくと思います（自宅のコンピューターにMatlabがないため、これをテストできません）。この問題は可能な限り高速になります。

于 2013-11-08T23:03:23.487 に答える
0

あなたの質問を解析しようとしています。「順列なし」と「10 20 30 40 50 60 70 80」は「80 70 60 50 40 30 20 10」と同等であり、18 から 8 つの数値をサンプリングする必要があり、同じサンプルを 2 回サンプリングする必要はないと推測します。

これは、可能なすべての組み合わせ (18 の可能な値から 8 つのサンプル) を生成し、それらから選択することを意味します。これを行う方法は 43758 通りしかありません。その後、順列を含める必要があります。したがって、記載されている問題は（正しく理解している場合）解決できません。

質問が更新されたので編集します。次の方法が解決策になると思います。

lover_bound = 10;
upper_bound = 180;
steps = 10;
NumeroCestelli = 8; 

livello = [lover_bound:steps:upper_bound];
livello = [livello livello];

PianoSperimentale = combnk(livello, 8);

すべての数字は 2 回出現するため、繰り返すことができます。残念ながら、それは複数の「double」を許可し (たとえば [10 10 20 20 30 30 40 40] が許可されます)、これは計算された式よりもはるかに大きな数になります (つまり、36!/(28!8!) ~ 30M ）。可能なアプローチ (最大 1 つの double を許可する) は次のとおりです。

livello = lover_bound:steps:upper_bound;

for ii = 1:numel(livello)
  PS(ii,:,:) = combnk([livello livello(ii)], 8);
end

PianoSperimentale = reshape(PS, [], 8);

18 * (19!/(19-8)!8!) = 1360476これにより、「ループごとに1つの重複した数字」が可能になり、組み合わせの数はあなたの表現より少し大きくなりますが、あなたが考えていた答えに近づくと思います。このコンピューターにMatlabがないため、今はこれをテストできません...

于 2013-11-08T15:46:57.367 に答える