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

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.