2

ライン上に配置する必要がある多数のブロックがあるアプリケーションに取り組んでいます。つまり、さまざまな数のブロックがあり、それぞれが異なる長さで、ライン上に配置する必要があります。ブロック間には少なくとも 1 つの空の要素が必要です。

ライン上のブロックのすべての可能な順列を効率的に取得したいと思います。

たとえば、長さ 15 のラインがあり、サイズ 1、6、および 1 のブロックを配置したいとします。

順序が重要です。つまり、私の例では、1 サイズのブロックは常に 6 サイズのブロックの左右にある必要があります。

可能な順列は

X.XXXXXX.X.....
X..XXXXXX.X....
...
.....X.XXXXXX.X

Java などの高水準言語で可能なすべての順列を効率的に生成するにはどうすればよいですか?

4

3 に答える 3

3

これを行う 1 つの方法は、再帰的にアプローチすることです。

  1. すべてのブロックを格納するために必要な最小の合計長が、それらの間にちょうど 1 つのスペースがある場合、使用可能なスペースを超える場合、ブロックを配置する方法はありません。
  2. それ以外の場合、配置するブロックがない場合、ブロックを配置する唯一の方法は、すべての正方形を埋めないままにすることです。
  3. それ以外の場合は、2 つのオプションがあります。最初に、最初のブロックを行の最初の位置に配置し、行の先頭に余分な空白を 1 つ残してから、残りのブロックを行内の残りのスペースに再帰的に配置することができます。次に、行の最初のスペースを空白のままにして、行の残りのスペースに同じブロックのセットを再帰的に配置することができます。両方のオプションを試して、結果を組み合わせることで、探している答えが得られるはずです。

この再帰ロジックを実際の Java に変換することは、それほど難しくありません。以下のコードは読みやすくするために設計されており、少し最適化できます。

public List<String> allBlockOrderings(int rowLength, List<Integer> blockSizes) {
    /* Case 1: Not enough space left. */
    if (spaceNeededFor(blockSizes) > rowLength)) return Collections.EMPTY_LIST;

    List<String> result = new ArrayList<String>();

    /* Case 2: Nothing to place. */
    if (blockSizes.isEmpty()) {
        result.add(stringOf('.', rowLength));
    } else {
        /* Case 3a: place the very first block at the beginning of the row. */
        List<String> placeFirst = allBlockOrderings(rowLength - blockSizes.get(0) - 1,
                                                    blockSizes.subList(1, blockSizes.length()));
        for (String rest: placeFirst) {
             result.add(stringOf('X', blockSizes.get(0)) + rest);
        }

        /* Case 3b: leave the very first spot open. */
        List<String> skipFirst = allBlockOrderings(rowLength - 1, blockSizes);
        for (String rest: skipFirst) {
             result.add('.' + rest);
        }
    }
    return result;
}

spaceNeededFor指定されたブロックのリストを保持できる最短の行の長さを返すメソッドとstringOf、文字と数字を受け取り、その数のコピーの文字列を返すメソッドを実装する必要があります。与えられたキャラクター。

お役に立てれば！

于 2013-01-03T09:24:08.480 に答える
1

私には、この問題を別の方法で考える方が簡単に思えます。

ドットで区切られた、固定された順序で固定されたブロックがあります。残りのドットを許可された位置に分散することで、すべての順列を作成できます。

線のこの固定部分の長さは次のとおりです。

fixed_len = length_of_all_blocks + number_of_blocks - 1

残りのドット数は

free_dots = length_of_line - fixed_len.

オープンポジション数は

pos_count = number_of_blocks + 1

ここで、free_dots を pos_count に入れる方法の順列をすべて見つける必要があります。

于 2013-01-03T09:50:42.897 に答える
0

出力が非常に大きくなる可能性があるため、「効率的な実装」とは何かを判断するのは非常に困難です。したがって、高速な実装でさえ十分に高速ではありません。

そのようなタスクには、動的プログラミングと再帰のテクニックを使用します。再帰関数は、未使用の数値のリストと行の残りの長さの 2 つのパラメーターを取る必要があります。内部は単純なループになります。すでにわかっている結果を保存する必要があります。細かいところまで自分で処理できると思います。編集：私たちの友人はすでにそれを行っています:-)。

ところで、そのような仕事の目的は何ですか？すべての行と列にそのような番号があり、画像をデコードする必要があるグリッド内の画像については、私には残っています。このような問題を解決するためのより良い方法があります。

于 2013-01-03T09:30:41.813 に答える