3

こんにちは、すべての可能な数列をウォークスルーし、関数を介してシーケンスを渡す関数を構築しようとしています。それが true を返す場合は停止します。

マークアップは次のとおりです。

function sequences($smallest, $biggest, $long, $func) {
   $seq = array(); // Will have $long values 
   /*
    * generates the sequence
   */

   if (call_user_func($functions[$func])) {
      return $seq;
   } else {
      //generate next sequence.
   }

}

生成されたシーケンスには、整数から整数までの$long 一意の値が含まれ、ソートする必要があります。例:$smallest$biggest

/* $long = 4; $smallest = 5, $biggest = 10;
 * 
 * 5,6,7,8
 * 5,6,7,9
 * 5,6,7,10
 * 5,6,8,9
 * 5,6,8,10
 * ...
 * 7,8,9,10
 *
 *
 * $long = 4; $smallest = 15, $biggest = 60;
 *
 * ...
 * 15,41,49,56
 * ...
 * 37,39,53,60
 * ...
 */

私はそれに頭を包むことができませんでした。これまでのところ、これを達成する唯一の方法は、ランダムに数値を生成し、毎回配列をソートすることではありませんでした。それは明らかに最善の方法ではありません。

他のプログラミング言語 (c++、C#、js、java) も素晴らしいでしょう。

ノート

  • オドメーターではなく、シーケンス内の重複した数字は許可されておらず、各インデックスの値は 9 より大きくてもかまいません。
  • いくつかの条件に対してシーケンスをテストし、True または False を返す関数は、実際の問題は重複なしでシーケンスを 1 つずつ生成することです。
4

1 に答える 1

1

指定したシーケンスを生成するのは楽しいチャレンジでした。

以下のこのコードは、あなたが望むことをするはずです(私は思います)。または、少なくとも、ニーズに合わせて変更できるはずです。sequences()関数がテスト関数$functions[$func]が返す最初のシーケンスのみを返すようにしたいのtrueか、それともこれまでのすべてのシーケンスを返すようにしたいのか、正確にはわかりませんでした。この例では、最初の「一致」のみが返されます (またはnull、一致が見つからなかった場合)。

このコードは、ジェネレーター関数 (および PHP 5.4 以降で使用可能な短い配列構文) を使用するため、PHP 5.5 以降が必要です。これを PHP 5.5.12 でテストしたところ、意図したとおりに動作するようです。必要に応じて、古いバージョンの PHP で動作するようにコードを変更することができます (ジェネレーター/yield の使用は避けてください)。実はPHPジェネレーター関数を書いたのはこれが初めてです。

sequenceGenerator()を使用して反復できる再帰的なジェネレーター関数ですforeach。

また、echoSequences()echo を使用して、生成されたすべてのシーケンスを順番に出力するだけのシーケンス生成をテストするための関数も作成しました。

function sequenceGenerator(array $items, $long = null, $level = 1, $path = null) {
    $itemCount = count($items);
    if (empty($long)) $long = $itemCount;
    if ($path == null) $path = [];

    if ($itemCount > 1) {
        foreach ($items as $item) {
            $subPath = $path;
            $subPath[] = $item;
            if ($level == $long) {
                yield $subPath;
                continue;
            }

            if (count($subPath) + count($items) > $long) {
                $items = array_values(array_diff($items, [$item]));
                $iteration = sequenceGenerator($items, $long, $level + 1, $subPath);
                foreach ($iteration as $value) yield $value;
            }
        }
    } elseif ($itemCount == 1) {
        $path[] = $items[0];
        yield $path;
    }
}

// Function for testing sequence generation
function echoSequences($smallest, $biggest, $long) {
    $items = range($smallest, $biggest);
    foreach (sequenceGenerator($items, $long) as $sequence) {
        echo implode(',', $sequence)."<br>\n";
    }
}

function sequences($smallest, $biggest, $long, $func) {
    global $functions;
    $items = range($smallest, $biggest);
    foreach (sequenceGenerator($items, $long) as $sequence) {
        if (call_user_func($functions[$func], $sequence)) {
            return $sequence;
        }
    }
    return null; // Return null when $func didn't return true for any sequence
}

//echoSequences(5, 10, 4); // Test sequence generation

$functions = array(
    // This test function returns true only for the sequence [5,6,8,10]
    'testfunc' => function($sequence) { return ($sequence == [5,6,8,10]); }
);

$sequence = sequences(5, 10, 4, 'testfunc'); // Find the first sequence that 'testfunc' will return true for (or null)
if (!empty($sequence)) {
    echo 'Found match: '.implode(',', $sequence);
} else {
    echo 'Match not found';
}
于 2015-05-06T16:51:21.463 に答える