五个位置的五个元素排列的最大子集，共有一个元素的位置相同

Question

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

我尝试了蛮力攻击，首先从排列的完整列表，3125个成员开始，然后逐个遍历list元素，并通过不合标准的步骤拒绝那些不符合条件的对象：

• 步骤1：针对元素1测试元素2至3125，获得新的较短列表L'
• 第一步：将元素3至N'与元素2'进行比较，得到更短的列表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.