6

の形式の文字列があります000011122222。つまり、連続した数字がランダムに繰り返されます。の回。他の例は次のとおりです。

0011122223333
01222    
00011234444
001122222

等々。たとえば、 string01222の場合、合計で5!/3!順列が可能であることを知っています。このような文字列ごとに、これらすべての順列を生成する必要があります。

さまざまな方法で順列を生成しようとしました。1 つは、すべての可能な順列を生成することです (繰り返しのない文字列の場合と同様)。ただし、使用する文字列は非常に大きくなる可能性があるため、冗長な順列を生成しすぎて時間を浪費する可能性があります。

次に、文字列のサイズに等しい文字配列のランダムなインデックスに数字を配置し、数字の数が入力文字列と同じになったらループを終了しようとしました。ただし、この方法では多くのメモリを浪費し、多くの時間を費やしています。

このような文字列の順列を効率的に生成する方法が必要です。アルゴリズムやコードだけでも構いません。私はJavaを使用しています。

ありがとう！

4

4 に答える 4

7

順列を生成するための標準的なアルゴリズムの 1 つは、それらを辞書式の昇順でリストするアルゴリズムです。C++ アルゴリズムのほとんどの実装で使用されるこのアルゴリズムは、std::next_permutation順列ごとに最大 O(n) 時間で順列を生成し、互いに重複しているすべての順列をスキップします。コードアップも非常に簡単です。

お役に立てれば！

于 2012-07-04T20:02:18.107 に答える
3

元の数字列を並べ替える代わりに、数字グループを並べ替えます。どのように説明すればよいか分からないので、疑似コードを試してみます。

文字列「001222」の場合、数字グループは 2 つの 0、1 つの 1、および 3 つの 2 です。

permute(groups, permutation):
    if there are no non-empty groups
        print permutation
    else
        for each non-empty group
            permutation += group.digit
            --group.count
            permute(groups, permutation)

すべての数字ではなくグループをループすることにより、各数字は複数回ではなく次の位置に 1 回だけ選択できるため、重複の生成が回避されます。あなたが得るランダムな順列を歩く

Permutation  Digit Groups

             0: 2, 1: 1, 2: 3  // start
0            0: 1, 1: 1, 2: 3
02           0: 1, 1: 1, 2: 2  // *
021          0: 1, 1: 0, 2: 2  // the 1 group is removed from the set
0212         0: 1, 1: 0, 2: 1
02120        0: 0, 1: 0, 2: 1  // the 0 group is removed from the set
021202       0: 0, 1: 0, 2: 0  // the 2 group is removed from the set

展開して * に戻ります。

02           0: 1, 1: 0, 2: 1

元の文字列のすべての (繰り返される) 数字ではなく、数字グループをループしているため、2 を再度選択することはできません。これは、プレフィックス「02」が一度だけ生成されるため、「02」で始まるすべての順列が一意になることを意味します。同じことがアルゴリズム全体に適用されます。

アップデート

入力 "001222" に対して 60 の順列を生成する簡単な PHP 実装を次に示します。

function permute(&$groups, &$count, $permutation) {
    $done = true;
    foreach ($groups as &$group) {
        if ($group[1] > 0) {
            --$group[1];
            permute($groups, $count, $permutation . $group[0]);
            ++$group[1];
            $done = false;
        }
    }       
    if ($done) {
        echo $permutation . PHP_EOL;
        ++$count;
    }
}

$groups = array(
    array(0, 2),
    array(1, 1),
    array(2, 3),
);
$count = 0;
permute($groups, $count, '');
echo "\nTotal: $count\n";
于 2012-07-04T20:24:21.010 に答える
0

桁数をランダムに選択して文字列を作成できます。このような：

length : int - Total string length
digits : int - maximum digit to include in the string
string : String - the return value
for(i : int from 0 to digits)
{
    remainingChars : int = length - length(string) //remaining chars in string
    remainingDigits : int = digits - i + 1
    count : int = Random from 1 to (remainingChars - remainingDigits + 1)
    Append count times i to the string
}
于 2012-07-04T20:09:52.687 に答える
0

あなたが何を言おうとしているのか正確にはわかりませんが、012 のような数字のセットがあり、すべての順列が次のようなバージョンの順列が必要だったことがあります。

012 021 102 120 201 210

これを達成するために、ウィキペディアhttp://en.wikipedia.org/wiki/Permutation を調べてアルゴリズムを見つけ、次のようなメソッドを作成しました。

    public static boolean Permute(int[] a) {
        int k, l, n = a.length -1;
        for (k = n -1; ; k--) {
            if (k == -1)
                return false;
            if (a[k] < a[k + 1])
                break;
        }
        for (l = n; l >= 0; l--) {
            if (a[k] < a[l]) {
                int opt = a[l];
                a[l] = a[k];
                a[k] = opt;
                break;
            }
        }
        for (int i = k + 1, j = n; i < j; i++, j--) {
            int opt = a[i];
            a[i] = a[j];
            a[j] = opt;
        }
        return true;
    }

具体的に教えていただけると助かります

于 2012-07-04T20:19:32.153 に答える