Самое длинное подмножество пятиэлементных перестановок из пяти позиций, общее только одноэлементное положение - PullRequest
Новая
       170

Самое длинное подмножество пятиэлементных перестановок из пяти позиций, общее только одноэлементное положение

4 голосов
/ 30 мая 2020

Я пытаюсь получить самый длинный список из набора из пяти упорядоченных позиций, от 1 до 5 каждая, удовлетворяющего условию, что любые два члена списка не могут иметь более одной идентичной позиции (индекса) . То есть 11111 и 12222 разрешены (используется только 1 в индексе 0), но 11111 и 11222 не разрешены (одинаковое значение в индексах 0 и 1).

Я пробовал атаку методом перебора, начиная с полного списка перестановок, 3125 членов и проходя по списку элемент за элементом, отклоняя те, которые не соответствуют критериям, в несколько этапов:

  • шаг первый: проверка элементов с 2 по 3125 против элемента 1, получение нового более короткого списка 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

1 Ответ

3 голосов
/ 30 мая 2020

Вот модель Picat для проблемы (насколько я понимаю): http://hakank.org/picat/longest_subset_of_five_positions.pi Она использует моделирование ограничений и решатель SAT.

Изменить: вот модель MiniZin c: 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.
...