1

この質問は、私の質問hereに関連しています。私の数学が正しいかどうかを確認するために、プログラムで次のカウントを取得しようとしています。

PQRDDDEEEEFFFFFF という単語の文字の並び方で、同じ文字が連続していないものはいくつありますか?

PHPプログラムを使用してこのカウントを決定する方法は?

私のアプローチ

  1. ヒープのアルゴリズムを使用してすべての可能な順列を生成し、配列に格納しました(ヒープのアルゴリズムがより高速に検出されるため、ヒープのアルゴリズムを使用しました)
  2. array_unique 関数を使用してすべての重複を削除しました
  3. 配列を反復処理し、正規表現 /(.)\1/ を使用して隣接する文字が同じである文字列を特定し、隣接する文字が同じでない文字列を新しい配列にコピーしました。
  4. 新しい配列には、必要な要素のリストがあります。

私のアプローチはうまく機能しています。ただし、大きな文字列 (10 文字を超える文字列) の場合、順列の数が多いためにメモリの問題が発生し、プログラムが機能しません。

これをプログラムで判断する別の方法はありますか?

ノート：

文字列のリストではなく、カウントのみを探しています

4

4 に答える 4

1

パイソン

Python は、ビッグ データに必要な大規模で複雑なデータセットを操作するための最も人気のあるオープン ソース (無料) 言語の 1 つです。柔軟性があり、比較的習得しやすいため、近年非常に人気があります。ほとんどの人気のあるオープン ソース ソフトウェアと同様に、製品を改善し、新しいユーザーに人気を持たせることに専念する大規模でアクティブなコミュニティもあります。無料の Code Academy コースでは、基本を 13 時間で学習できます。

ソース:

http://www.datasciencecentral.com/profiles/blogs/ten-top-languages-for-crunching-big-data https://www.continuum.io/why-python

于 2016-12-09T15:26:17.827 に答える
1

これは、指数関数的ではありますが、あなたのメソッドよりもはるかに効率的な Python です (申し訳ありませんが、PHP を知りません)。

from collections import Counter


def instancekey(letters):
    return tuple(sorted(Counter(letters).values()))


memo = {}


def permcount(letters):
    if not letters:
        return 1
    key = instancekey(letters)
    count = memo.get(key)
    if count is None:
        count = 0
        for letter, lettercount in Counter(letters).items():
            rest = letters
            for i in range(lettercount):
                j = rest.find(letter)
                rest = rest[:j] + rest[j + 1:]
                if i % 2 == 0:
                    count += permcount(rest)
                else:
                    count -= permcount(rest)
        memo[key] = count
    return count

ここには 2 つのアイデアがあります。1 つ目は、包含と除外を介して再帰的にカウントを実行することです。入力の文字ごとに、その文字で始まる可能性の数を累積します。単純に、残りの文字の可能性を数えるだけで十分ですが、これは最初の 2 文字が等しいという制約を強制しません。したがって、修正を適用します。つまり、2 つの文字が削除される可能性の数を引きます。この修正自体に修正が必要であり、その結果、包含除外式にたどり着きます。

2 番目のアイデアは、メモ化を使用して関数評価の数を大幅に削減することです。のような単語が与えられた場合PQRDDDEEEEFFFFF、数えます

P: 1
Q: 1
R: 1
D: 3
E: 4
F: 5

次に、文字をドロップして (重要ではないため)、値を並べ替えます。

1,1,1,3,4,5.
于 2016-12-09T17:31:18.097 に答える
0

純粋な方法は、ブルートフォースです。基数 N でカウントするだけです。ここで、N は個別の文字の数です。N 基数に必要な桁数は、文字の総数です。次に、許容される各文字の数に制約を適用し、同じ文字が 2 つ連続しないようにします。

きれいでも速くもありませんが、正しい答えが得られます。

ここにPHPがあります：

$letters = 'PQRDDDEEEEFFFFF';

$letter_counts = CountLetters($letters);

echo CountCombinations($letter_counts);

function CountLetters($letters) {
    $letter_counts = array();
    foreach (str_split($letters) as $letter) {
        if (isset($letter_counts[$letter])) {
            $letter_counts[$letter]++;
        } else {
            $letter_counts[$letter] = 1;
        }
    }
    return array_values($letter_counts);
}

function CountCombinations($allowable) {
    $max = count($allowable) - 1;
    $total_places = 0;
    for ($index = 0; $index <= $max; $index++) {
        $total_places += $allowable[$index];
    }

    $counter = array_fill(0, $total_places, 0);

    $combinations = 0;
    do {
        $ok = true;

        // count the number of each character in this combination
        $bins = array_fill(0, $max + 1, 0);
        for ($index = 0; $index < $total_places; $index++) {
            $bins[$counter[$index]]++;
        }

        // ensure the counts match the number allowable for each
        for ($index = 0; $index <= $max; $index++) {
            if ($bins[$index] != $allowable[$index]) {
                $ok = false;
                break;
            }

        }

        // ensure that no two consecutive are the same
        if ($ok) {
            for ($index = 0; $index <= ($total_places - 2); $index++) {
                if ($counter[$index] == $counter[$index + 1]) {
                    $ok = false;
                    break;
                }
            }
        }

        if ($ok) {
            $combinations++;
        }

        // find the next combination (i.e. count in base N)
        for ($index = 0; $index <= ($total_places - 1); $index++) {
            $counter[$index] = $counter[$index] + 1;
            if ($counter[$index] <= $max) {
                break;
            } else {
                $counter[$index] = 0;
            }
        }
    } while ($index < $total_places);

    return $combinations;
}
于 2016-12-12T10:38:37.820 に答える