DjangoBB LoFi version

1 2 3

Singularity

Янв. 19, 2013 20:35:09

EchoXSpace

Исправил.

Если “Камни можно свободно двигать по нитке” значит,
'aab', ‘aba’, ‘baa’ <= одно и тоже ?

Все таки формулу вывести правильней.

EchoXSpace

Янв. 19, 2013 21:20:33

Сочетание

То, что больше - брать за k.

Да, это одно и тоже.

sergeek

Янв. 20, 2013 11:23:28

import string
from itertools import product
def count_neck(n,k):
    make_neck = (neck for neck in product(string.hexdigits[:k],repeat=n))
    assert 0 < n*k < 33
    class Necklace:
        def __init__(self):
            self.neck = next(make_neck)
        def __eq__(self,other):            
            return hash(self) == hash(other) or self.neck == tuple(reversed(other.neck))
        def __hash__(self):
            return reduce(lambda x,y : x*int(''.join(self.neck[y:] + self.neck[:y]),k),range(n),1)
    return len({Necklace() for num in range(k**n)}) if n > 1 else k

EchoXSpace

Янв. 20, 2013 12:05:14

Спасибо!

Ну теперь буду разбирать, как это работает

Как адаптировать под python3?

sergeek

Янв. 20, 2013 12:36:33

добавить

from functools import reduce

но это не надо так как я там ошибся

. Вот проще без изъебств

import string
from itertools import product
def count_neck(n,k):
    assert 0 < n*k < 33
    s = set()
    res = 0
    for neck in product(string.ascii_letters[:k],repeat=n):
        if neck not in s:
            res +=1
            for m in range(n):
                s.add(neck[m:] + neck[:m])
            s.add(tuple(reversed(neck)))
    return res
            
print(count_neck(5,2))

sergeek

Янв. 20, 2013 13:59:05

нашел формулу с таблицей для сверки

EchoXSpace

Янв. 20, 2013 14:10:14

Спасибо тебе

sergeek

Янв. 20, 2013 14:30:15

да кстати, насколько я понял те результаты в таблице заголовок стобца которых с апострофом (не помню как нормально он называется) это с учетом “переворачивания” ожерелья, а которые без - те без учета. Так вот мои почему-то совпадают с теми которые без учета, и я не знаю почему

EchoXSpace

Янв. 20, 2013 16:01:39

Хм, я делал “в лоб” c 4 цветами и 3 камнями - все норм, все правильно.

UPD: Уверен, что все правильно. Просто выведи верные результаты.

UPD2: Окей

sergeek

Янв. 20, 2013 16:18:12

да не, на самом деле ошибка. Вот так полностью совпадает

import string
from itertools import product
def count_neck(n,k):
    assert 0 < n*k < 33
    s = set()
    res = 0
    for neck in product(string.ascii_letters[:k],repeat=n):
        if neck not in s:
            res +=1
            for m in range(n):
                shifted = neck[m:] + neck[:m]
                s.add(shifted)
                s.add(tuple(reversed(shifted)))
    return res
for k in range(2,4):
    for n in range(1,16):
        print('{} {} --> {}'.format(n,k,count_neck(n,k)))