五位置五元素排列的最长子集，只有一个元素位置是共同的

Question

我正在尝试获取最长一组五个有序位置的列表，每个1到5个，满足列表中任何两个成员不能共享超过的条件一个相同的位置（索引）。即，允许使用 11111 和 12222（仅共享索引 0 处的 1），但不允许使用 11111 和 11222（索引 0 和 1 处的值相同）。

我尝试了暴力攻击，从完整的排列列表开始，有 3125 个成员，然后逐个元素遍历列表，拒绝不符合条件的元素，分为几个步骤：

第一步：针对元素 1 测试元素 2 到 3125，得到一个新的较短列表 L'
第一步：针对元素 2' 测试元素 3 到 N'，得到更短的列表 L''，

等等。

我得到一个 17 成员的解决方案，完全有效。问题是：

我知道至少有两个 25 成员的有效解决方案是幸运的，
这种暴力方法的解决方案在很大程度上取决于 3125 个成员列表的初始顺序，所以我已经能够找到 12 到 21 个成员的解决方案，洗牌 L0 列表，但我从来没有命中 25 个成员的解决方案。

谁能解释一下这个问题？谢谢。

这是我目前的方法

import csv, random 

maxv = 0
soln=0

for p in range(0,1): #Intended to run multiple times 

    z = -1  

    while True:

        z = z + 1

        file1 = 'Step' + "%02d" % (z+0) + '.csv'
        file2 = 'Step' + "%02d" % (z+1) + '.csv'

        nextdata=[]

        with open(file1, 'r') as csv_file:
            data = list(csv.reader(csv_file))


        #if file1 == 'Step00.csv':  # related to p loop
        #    random.shuffle(data)


        i = 0
        while i <= z:        
            nextdata.append(data[i])        
            i = i + 1


        for j in range(z, len(data)):

            sum=0
            for k in range(0,5):

                if (data[z][k] == data[j][k]):
                    sum = sum + 1

            if sum < 2:
                nextdata.append(data[j])


        ofile = open(file2, 'wb')
        writer = csv.writer(ofile)
        writer.writerows(nextdata) 
        ofile.close()

        if (len(nextdata) < z + 1 + 1):
            if (z+1)>= maxv:
                maxv = z+1
                print maxv
                ofile = open("Solution"+"%02d" % soln + '.csv', 'wb')
                writer = csv.writer(ofile)
                writer.writerows(nextdata) 
                ofile.close()
            soln = soln + 1
            break

Answer 1

这是问题的 Picat 模型（据我了解）：http://hakank.org/picat/longest_subset_of_five_positions.pi 它使用约束建模和 SAT 求解器。

编辑：这是一个 MiniZinc 模型：http://hakank.org/minizinc/longest_subset_of_five_positions.mzn

模型（谓词 go/0）检查 2 到 100 的长度。2 到 25 之间的所有长度至少有一个解决方案（可能更多）。所以25是最长的子序列。这是一个 25 长度的解决方案：

{1,1,1,3,4}
{1,2,5,1,5}
{1,3,4,4,1}
{1,4,2,2,2}
{1,5,3,5,3}
{2,1,3,2,1}
{2,2,4,5,4}
{2,3,2,1,3}
{2,4,1,4,5}
{2,5,5,3,2}
{3,1,2,5,5}
{3,2,3,4,2}
{3,3,5,2,4}
{3,4,4,3,3}
{3,5,1,1,1}
{4,1,4,1,2}
{4,2,1,2,3}
{4,3,3,3,5}
{4,4,5,5,1}
{4,5,2,4,4}
{5,1,5,4,3}
{5,2,2,3,1}
{5,3,1,5,2}
{5,4,3,1,4}
{5,5,4,2,5}

有很多不同的 25 长度解决方案（谓词 go2/0 检查）。

这是完整的模型（根据上面的文件编辑）：

import sat.
main => go.

%
% Test all lengths from 2..100.
% 25 is the longest.
%
go ?=>
  nolog,
  foreach(M in 2..100)
  println(check=M),
  if once(check(M,_X)) then
    println(M=ok)
  else
    println(M=not_ok)
  end,
  nl
end,
nl.

go => true.


%
% Check if there is a solution with M numbers
% 
check(M, X) =>
  N = 5,
  X = new_array(M,N),
  X :: 1..5,

  foreach(I in 1..M, J in I+1..M)
    % at most 1 same number in the same position
    sum([X[I,K] #= X[J,K] : K in 1..N]) #<= 1, 
    % symmetry breaking: sort the sub sequence
    lex_lt(X[I],X[J])
  end,

 solve([ff,split],X),

 foreach(Row in X)
   println(Row)
 end,
 nl.

五位置五元素排列的最长子集，只有一个元素位置是共同的

Longest subset of five-positions five-elements permutations, only one-element-position in common

python

constraints

permutation

minizinc