3

各文字列を最大1回使用して、一連の文字列の可能なすべての組み合わせを生成しようとしています。

  • 出力文字列の長さは定義されていません (一度しか使用できないため、最大長は指定された文字列の数です)
  • たとえば、文字列セットarray('A','B')は A、B、AB、BA を生成します。
  • たとえば、文字列セットarray('ABC', 'Z')は「ABC」、「Z」、「ZABC」、および「ABCZ」を生成します。
  • 文字列セットは同一のエントリを持つことができ、出力は一意である必要はありません。たとえば、文字列セットarray('A', 'A')は 'A'、'A'、'AA'、'AA' を生成します。（実際には重複は必要ありませんが、物事をより難しくしたくありません）

2 つの文字列には 4 つの組み合わせ (2=>4) と 3=>15、4=>64、5=>325 ... があることを知っています。

私はプログラマーではないので、少なくとも「やりがいがある」と感じました。ネストされたループはすぐに複雑になりすぎます。より簡単な解決策は、文字列を含む配列のインデックスでパターンを見つけることです。しかし、これにより、文字列を重複して使用できます...

  $strings = array('T','O','RS');
  $num = 0;
  $stringcount = count($strings);
  $variations = array(0,1,4,15,64,325,1956,13699,109600,986409);

  for($i=0;$i<$variations[$stringcount];$i++){
    $index = base_convert($num, 10, $stringcount);
    $array_of_indexes = str_split($index);
    $out='';
    for($j=0;$j<count($array_of_indexes);$j++){
     $out .= $strings[$array_of_indexes[$j]];
    }
    echo $out . '<br />';
    $num++;
  }

結果: TORS OT OO ORS RST RSO RSRS OTT OTO OTRS OOT OOO OORS

良くない、多くの重複 + 多くの有効な組み合わせが含まれていません

この解決策が多くの点で間違っていることはわかっていますが、どこから始めればよいかわかりません。助言がありますか？事前にt​​hx！

4

4 に答える 4

3

数学用語では、入力セットの可能なすべての空でない順序付けられたサブセットを求めています。整数シーケンスのオンライン百科事典では、そのようなシーケンスの数はシーケンス A007526として表示されます。このシーケンスは、発見したとおり、4、15、64、325 で始まることに注意してください。

この問題は、Python で非常に短く効率的な解決策を認めているため、最初にその解決策を投稿します。

def gen_nos(s):
    for i in sorted(s):
        yield i
        s.remove(i)
        for j in gen_nos(s):
            yield i+j
        s.add(i)

例：

>>> list(gen_nos(set(['a', 'b', 'c'])))
['a', 'ab', 'abc', 'ac', 'acb', 'b', 'ba', 'bac', 'bc', 'bca', 'c', 'ca', 'cab', 'cb', 'cba']

sorted厳密には必要ないことに注意してください。出力が辞書順でソートされることを保証するだけです (それ以外の場合、要素は設定された順序で反復されますが、これは本質的に任意です)。

これを PHP に変換するには、結果を保持するための追加の配列パラメーターを持つ再帰関数を基本的に使用する必要があります。

function gen_nos(&$set, &$results) {
    for($i=0; $i<count($set); $i++) {
        $results[] = $set[$i];
        $tempset = $set;
        array_splice($tempset, $i, 1);
        $tempresults = array();
        gen_nos($tempset, $tempresults);
        foreach($tempresults as $res) {
            $results[] = $set[$i] . $res;
        }
    }
}

例：

$results = array();
$set = array("a", "b", "c");
gen_nos($set, $results);
var_dump($results);

生産する

array(15) {
  [0]=>
  string(1) "a"
  [1]=>
  string(2) "ab"
  [2]=>
  string(3) "abc"
  [3]=>
  string(2) "ac"
  [4]=>
  string(3) "acb"
  [5]=>
  string(1) "b"
  [6]=>
  string(2) "ba"
  [7]=>
  string(3) "bac"
  [8]=>
  string(2) "bc"
  [9]=>
  string(3) "bca"
  [10]=>
  string(1) "c"
  [11]=>
  string(2) "ca"
  [12]=>
  string(3) "cab"
  [13]=>
  string(2) "cb"
  [14]=>
  string(3) "cba"
}
于 2012-08-28T14:39:10.077 に答える
1

これは、組み合わせと順列の基本的な数学的定義を使用してかなり長い間書いてきた私の実装です。多分これが役立つかもしれません。

<?php
/**
 * Generate all the combinations of $num elements in the given array
 *
 * @param array  $array   Given array
 * @param int    $num     Number of elements ot chossen
 * @param int    $start   Starter of the iteration
 * @return array          Result array
 */
function combine($array, $num, $start = 0) {

    static $level = 1;

    static $result = array();

    $cnt = count($array);

    $results = array();

    for($i = $start;$i < $cnt;$i++) {
        if($level < $num ) {
            $result[] = $array[$i];
            $start++;
            $level++;
            $results = array_merge($results, combine($array, $num, $start));
            $level--;
            array_pop($result);
        }
        else {
            $result[] = $array[$i];
            $results[] = $result;
            array_pop($result);
        }
    }

    return $results;
}

/**
 * Generate all the permutations of the elements in the given array
 */
function permute($array) {

    $results = array();

    $cnt = count($array);

    for($i=0;$i<$cnt;$i++) {
        $first = array_shift($array);

        if(count($array) > 2 ) {
            $tmp = permute($array);
        }
        elseif(count($array) == 2) {
            $array_ = $array;
            krsort($array_);
            $tmp = array($array, $array_);
        }
        elseif(count($array) == 1) {
            $tmp = array($array);
        }
        elseif(count($array) == 0) {
            $tmp = array(array());
        }

        foreach($tmp as $k => $t) {
            array_unshift($t, $first);
            $tmp[$k] = $t;
        }

        $results = array_merge($results, $tmp);

        array_push($array, $first);
    }

    return $results;
}

$strings = array('T', 'O', 'RS');
$strings_count = count($strings);


$combinations = array();
for ($i = 1; $i <= $strings_count; $i++) {
  $combination = combine($strings, $i, 0);
  $combinations = array_merge($combinations, $combination);
}

$permutations = array();
foreach($combinations as $combination) {
  $permutation = permute($combination);
  $permutations = array_merge($permutations, $permutation);
}

print_r($combinations);
print_r($permutations);
于 2012-08-28T15:28:48.883 に答える
0

これが私の素朴な再帰的実装です：

<?php
// Lists all ways to choose X from an array
function choose($x, array $arr) {
    $ret = array();
    if ($x === 0) {
        // I don't think this will come up.
        return array();
    } else if ($x === 1) {
        foreach ($arr as $val) {
            $ret[] = array($val);
        }
    } else {
        $already_chosen = choose($x - 1, $arr);
        for ($i = 0, $size_i = sizeof($arr); $i < $size_i; $i++) {
            for ($j = 0, $size_j = sizeof($already_chosen); $j < $size_j; $j++) {
                if (!in_array($arr[$i], $already_chosen[$j])) {
                    $ret[] = array_merge(
                        array($arr[$i]),
                        $already_chosen[$j]
                    );
                }
            }
        }
    }
    return $ret;
}

function choose_all($arr) {
    for ($i = 1, $size = sizeof($arr); $i <= $size; $i++) {
        foreach (choose($i, $arr) as $val) {
            echo implode(":", $val).PHP_EOL;
        }
    }
}

choose_all(array(
    "A",
    "B",
));
echo "--".PHP_EOL;
choose_all(array(
    "ABC",
    "Z",
));
echo "--".PHP_EOL;
choose_all(array(
    'T',
    'O',
    'RS'
));

（もちろん、何をしたかはわかりません）

http://codepad.org/5OKhsCJg

于 2012-08-28T14:39:31.127 に答える
-2

アレイ上で必要なのは、本質的にデカルト積です。これは集合数学の側面であり、データベースシステムや正式なモデリング言語で一般的です。この用語をPHPでグーグルすると、多くの実装ソリューションがあります。

（私はPHPを直接行ったことがないので、間違った（またはハッキーな）ソリューションを投稿したくありませんが、これが正しい道をたどるのに役立つことを願っています）！

于 2012-08-28T14:06:10.437 に答える