1

次の制約に従って値のマトリックスのような (リストのリスト) を配置する (またはそれが不可能であると判断する) 驚くほど困難な問題に遭遇しました。

最大 n 個の異なる値 (行内での繰り返しなし) を持つランダムに生成された m 行のマトリックスは、次のようにマトリックスを配置します (可能な場合)。

1) 行列は「下三角」でなければなりません。「ギャップ」だけが右上隅にあるように、行は長さの昇順で並べる必要があります。

2) 値が複数の行に表示される場合、同じ列にある必要があります (つまり、行内の値の順序を並べ替えることができます)。

問題/解決策を関数型言語 (Scala など) で表現することが望ましい。

例 1 - 解決策がある

AB
CED
CAB

となる（ひとつの解として）

AB
EDC
ABC

A、B、および C はすべて、それぞれ列 1、2、および 3 に表示されるためです。

例 2 - 解決策がない

ABC
ABD
BCD

制約により、3 番目の行の 3 番目の列に C と D を含める必要があるため、解決策はありませんが、これは不可能です。

4

2 に答える 2

1

これは興味深い問題だと思い、正しいと思われる MiniZinc (非常に高レベルの制約プログラミング システム) で概念実証バージョンをモデル化しました。それが役に立つかどうかはわかりませんし、正直なところ、非常に大きな問題のインスタンスに対して強力かどうかもわかりません.

このモデルによると、最初の問題のインスタンスには 4 つの解決策があります。

 B A _
 E D C
 B A C
 ----------
 B A _
 D E C
 B A C
 ----------
 A B _
 E D C
 A B C
 ----------
 A B _
 D E C
 A B C

2 番目の例は、満足できないと見なされます (そうあるべきです)。

完全なモデルはこちら: http://www.hakank.org/minizinc/ordering_a_list_of_lists.mzn

基本的なアプローチは、行列を使用することです。短い行は null 値 (ここでは 0、ゼロ) で埋められます。問題のインスタンスは、マトリックス「マトリックス」です。結果として得られる解は、行列 "x" (出力で文字列に変換される整数としての決定変数) にあります。次に、「x」の各行が「matrix」の対応する行の順列であることを保証するために使用されるヘルパー マトリックス「perms」があり、述語「permutation3」で実行されます。制約を簡素化するヘルパー配列/セットが他にもいくつかあります。

主な MiniZinc モデル (出力なし) を以下に示します。

モデルを役に立たなくする可能性のあるコメント/仮定を次に示します。

  • 興味深い問題だと思ったので、これは単なる概念実証モデルです。

  • 行列 (問題データ) の行は既にサイズ (下三角) で並べられていると仮定します。これは、制約プログラミングが不要な前処理ステップとして簡単に実行できるはずです。

  • 短いリストは 0 (ゼロ) で満たされているため、行列を操作できます。

  • MiniZinc は厳密に型指定された言語であり、記号をサポートしていないため、文字 A..E を表す整数 1..5 を定義するだけです。整数の操作は、従来の制約プログラミング システムを使用する場合にも役立ちます。

    % MiniZinc モデル (sans 出力)
    「globals.mzn」を含めます。
    整数: 行 = 3;
    整数: 列 = 3;

    整数: A = 1;
    整数: B = 2;
    整数: C = 3;
    整数: D = 4;
    整数: E = 5;
    int: max_int = E;

    文字列の配列[0..max_int]: str = array1d(0..max_int, ["_", "A","B","C","D","E"]);

    % 問題 A (充足可能)
    配列 [1..行、1..列] の int: 行列 =
       array2d(1..行、1..列、
       [
         A,B,0, % この短い配列を「0」で埋める
         E、D、C、
         A、B、C、
       ]);

     % 有効な値 (0、ゼロをスキップします)
     int のセット: 値 = {A,B,C,D,E};

     % 特定の値がどの行であるかを識別します。
     % 問題 A の例:
     % value_rows: [{1, 3}, {1, 3}, 2..3, 2..2, 2..2]
     int のセットの配列 [1..max_int]: value_rows =
           [ {i | i は 1..rows、j は 1..cols where matrix[i,j] = v} | v in 値];


     % 決定変数
     % 結果の行列
     var 0..max_intの配列[1..行、1..列]: x;

     % 行列から x への順列
     var 0..max_int の配列 [1..rows、1..cols]: perms;


     %
     % permutation3(a,p,b)
     %
     % 順列 p を使用して ab から順列を取得します。
     %  
     predicate permutation3(array[int] of var int: a,
                            var int: p の array[int]
                            var int の array[int]: b) =
         forall(index_set(a) の i) (
            b[i] = a[p[i]]
         )
     ;

     解決する;満足する;

     制約
        forall(i in 1..rows) (
           % x と perms の行の値の単一性を保証します (0 を除く)
           alldifferent_except_0([x[i,j] | j in 1..cols]) /\
           alldifferent_except_0([perms[i,j] | j in 1..cols]) /\          
           permutation3([matrix[i,j] | j in 1..cols], [perms[i,j] | j in 1..cols], [x[i,j] | j in 1..cols])
        )
        /\ % x のゼロは、行列にゼロがある場所です
        forall(i in 1..rows, j in 1..cols) (
           行列[i、j] = 0の場合
              x[i,j] = 0
           そうしないと
              真実
           終了
        )

        /\ % 同じ値が同じ列にあることを確認します:
           % - 各値
           % - 1 つの列に配置されていることを確認します c
           forall(k in 1..max_int where k in values) (
              exists(j in 1..cols) (
                 forall(value_rows[k] の i) (
                   x[i,j] = k
                 )
              )
           )
       ;

       ％ 出力
       % ...
于 2013-09-04T19:26:40.720 に答える
0

関数型言語 (XQuery) でのソリューションが必要だったので、その表現力から Scala で最初に実装し、以下のコードを投稿しました。これは、ブルート フォースの幅優先スタイルのソリューション検索を使用します。私は単一のソリューション (存在する場合) に非常に興味があるため、アルゴリズムは余分なソリューションを破棄します。

def order[T](listOfLists: List[List[T]]): List[List[T]] = {

def isConsistent(list: List[T], listOfLists: List[List[T]]) = {
  def isSafe(list1: List[T], list2: List[T]) =
    (for (i <- list1.indices; j <- list2.indices) yield
      if (list1(i) == list2(j)) i == j else true
      ).forall(_ == true)

  (for (row <- listOfLists) yield isSafe(list, row)).forall(_ == true)
}


def solve(fixed: List[List[T]], remaining: List[List[T]]): List[List[T]] =
  if (remaining.isEmpty)
    fixed        // Solution found so return it
  else
    (for {
      permutation <- remaining.head.permutations.toList
      if isConsistent(permutation, fixed)
      ordered = solve(permutation :: fixed, remaining.tail)
      if !ordered.isEmpty
    } yield ordered) match {
      case solution1 :: otherSolutions =>       // There are one or more solutions so just return one
        solution1

      case Nil =>   // There are no solutions
        Nil
    }


// Ensure each list has unique items (i.e. no dups within the list)
  require (listOfLists.forall(list => list == list.distinct))

  /* 
   * The only optimisations applied to an otherwise full walk through all solutions is to sort the list of list so that the lengths 
   * of the lists are increasing in length and then starting the ordering with the first row fixed i.e. there is one degree of freedom
   * in selecting the first row; by having the shortest row first and fixing it we both guarantee that we aren't disabling a solution from being
   * found (i.e. by violating the "lower triangular" requirement) and can also avoid searching through the permutations of the first row since
   * these would just result in additional (essentially duplicate except for ordering differences) solutions.
   */
    //solve(Nil, listOfLists).reverse           // This is the unoptimised version
    val sorted = listOfLists.sortWith((a, b) => a.length < b.length)
    solve(List(sorted.head), sorted.tail).reverse
}
于 2013-09-29T23:51:27.690 に答える