Не понимаю результатов, полученных с помощью itertools.permutations () - PullRequest
Новая
       16

Не понимаю результатов, полученных с помощью itertools.permutations ()

0 голосов
/ 07 марта 2019

Это код, представляющий набор различных чисел от 0 до 15 в 12 разряде, так что различия между некоторыми соседними числами также различны. 

import itertools

list = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]

for i in itertools.permutations(list,12):
    a1 = abs(i[0] - i[1])
    b1 = abs(i[0] - i[2])
    a = abs(i[0] - i[3])
    b = abs(i[0] - i[4])
    c = abs(i[0] - i[5])
    d = abs(i[1] - i[6])
    e = abs(i[2] - i[7])
    f = abs(i[3] - i[8])
    g = abs(i[4] - i[9])
    h = abs(i[5] - i[10])
    g1 = abs(i[6] - i[11])
    h1 = abs(i[7] - i[11])
    c1 = abs(i[8] - i[11])
    d1 = abs(i[9] - i[11])
    e1 = abs(i[10] - i[11])
    L= [a1, b1, a, b, c, d, e, f, g, h, g1, h1, c1, d1, e1]
    if (len(set(L))==15):
        print(i)
        print(L)

Кажется, для этого нет выходных данныхкод, но я не могу понять, почему.

1 Ответ

1 голос
/ 07 марта 2019

Вот подход, который генерирует случайные решения. Он перемещает все проверки переменных в цикл и замыкает цикл при столкновении: 

import itertools, random

labels = list(range(16))
edges = ((0,1),(0,2),(0,3),(0,4),(0,5),(1,6),(2,7),(3,8),(4,9),(5,10),(6,11),(7,11),(8,11),(9,11),(10,11))
num_vertices = 12

def solve(labels,edges,num_vertices):
    shuffled_labels = labels[:] #make a copy
    random.shuffle(shuffled_labels)
    for p in itertools.permutations(shuffled_labels,num_vertices):
        differences = [0]*16
        solved = True #innocent until proven guilty
        for i,j in edges:
            difference = abs(p[i]-p[j])
            differences[difference] += 1
            if differences[difference] == 2:
                solved = False
                break #no need to check more edges
        if solved:
            return p

Один прогон (около 1 минуты): 

>>> solve(labels,edges,num_vertices)
(6, 5, 1, 14, 3, 2, 11, 15, 12, 13, 9, 0)

Это легко проверить, чтобы удовлетворить ваши ограничения.

Вот генераторное решение, которое даст все возможные решения: 

def solutions(labels,edges,num_vertices):
    for p in itertools.permutations(labels,num_vertices):
        differences = [0]*16
        solved = True #innocent until proven guilty
        for i,j in edges:
            difference = abs(p[i]-p[j])
            differences[difference] += 1
            if differences[difference] == 2:
                solved = False
                break #no need to check more edges
        if solved:
            yield p

Используется как, например ::

for p in solutions(labels,edges,num_vertices): print(p)

В отличие от случайного подхода, который обычно возвращается менее чем за минуту, генератор отрабатывает в течение очень долгого времени, прежде чем он начнет давать результаты. Это говорит о том, что перестановка тождеств (где начинается этот генератор) далека от решения. Тем не менее, он в конечном итоге приводит к перестановкам (примерно через 10-15 минут), первая из которых: 

(0, 1, 3, 13, 14, 15, 10, 7, 6, 2, 4, 12)

(согласен с результатом @jasonharper).

...