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

user_4405167 0
Viewed 137

I am trying to get the longest list of a set of five ordered position, 1 to 5 each, satisfying the condition that any two members of the list cannot share more than one identical position (index). I.e., 11111 and 12222 is permitted (only the 1 at index 0 is shared), but 11111 and 11222 is not permitted (same value at index 0 and 1).

I have tried a brute-force attack, starting with the complete list of permutations, 3125 members, and walking through the list element by element, rejecting the ones that do not match the criteria, in several steps:

  • step one: testing elements 2 to 3125 against element 1, getting a new shorter list L'
  • step one: testing elements 3 to N' against element 2', getting a shorter list yet L'',

and so on.

I get a 17 members solution, perfectly valid. The problem is that:

  • I know there are, at least, two 25-member valid solution found by a matter of good luck,
  • The solution by this brute-force method depends strongly on the initial order of the 3125 members list, so I have been able to find from 12- to 21-member solutions, shuffling the L0 list, but I have never hit the 25-member solutions.

Could anyone please put light on the problem? Thank you.

This is my approach so far

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
minizinc permutation constraints python
1 Answers

Here is a Picat model for the problem (as I understand it): http://hakank.org/picat/longest_subset_of_five_positions.pi It use constraint modelling and SAT solver.

Edit: Here is a MiniZinc model: http://hakank.org/minizinc/longest_subset_of_five_positions.mzn

The model (predicate go/0) check lengths of 2 to 100. All lengths between 2 and 25 has at least one solution (probably at lot more). So 25 is the longest sub sequence. Here is one 25 length solution:

{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}

There is a lot of different 25 lengths solutions (the predicate go2/0 checks that).

Here is the complete model (edited from the file above):

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.
user_1956360
Related