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

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

这是该问题的皮卡模型(据我所知(： http://hakank.org/picat/longest_subset_of_five_positions.pi 它使用约束建模和 SAT 求解器。

编辑：这是一个迷你锌模型：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.