三色七珠手链问题

markfang2050

northwolves 发表于 2019-10-20 20:05
Returns:

1 4

这个 错的。7颗，198种是对的。

markfang2050

珠宝商一共有198种独一无二的彩珠手链出售。
------------------------------------------------------------
python3.6程序运行 0.2848389148712158 秒。
------------------------------------------------------------

markfang2050

import time
import matplotlib.pyplot as plt
import numpy as np
import time
time_start=time.time()#计算时间开始

counter=0;
def draw_nklc(nk,n):
    plt.close()
    fig = plt.figure()
    ax1=fig.add_subplot(111)
    ang = np.arange(0,2*np.pi,2*np.pi/7)
    plc= [(12*np.cos(theta),16*np.sin(theta)) for theta in ang]
    for i in range(7):
        bll=plt.Circle(plc[i],3,color = nk[i])
        ax1.add_patch(bll)
    plt.xlim((-30,30))
    plt.ylim((-30,30))
    plt.savefig('三色珠'+str(n)+'.png')

bc_st=('red','green','blue')                #总共三种颜色
nk_lc=[(x1,x2,x3,x4,x5,x6,x7)\
       for x1 in bc_st\
       for x2 in bc_st\
       for x3 in bc_st\
       for x4 in bc_st\
       for x5 in bc_st\
       for x6 in bc_st\
       for x7 in bc_st]                     #列出所有可能的序列，共计2184种序列


ns = list()                                 #建立新的序列集合

for item in nk_lc:                          #将原序列集合的元素添加至新序列集合
    fg = 1
    a = [item[i:]+item[:i]\
         for i in range(len(item))]         #添加前检查元素是否已在新序列中
    for it in a:                            #检查时先将序列循环旋转一遍
        if it in ns:
            fg = 0
            break
    if fg == 1:
        c = tuple([x for x in\
                   reversed(item)])         #然后将元素倒序再次循环旋转一遍依次检查
        b = [c[i:]+c[:i]\
             for i in range(len(c))]
        for it in b:
            if tuple(it) in ns:
                fg = 0
                break
    if fg ==1:
        ns.append(item)
        counter += 1 # 计算个数.

        

#for i in range(len(ns)):
    #draw_nklc(ns[i],i)

print('-'*60)

print('珠宝商一共有%d种独一无二的彩珠手链出售。'%(counter))
print('-'*60)
time_end=time.time()#计算时间结束
print('python3.6程序运行',time_end-time_start,'秒。')
print('-'*60)

northwolves

1. import numpy as np
   
2. 
   
3. def count(n):
   
4. 
   
5.     m=0
   
6. 
   
7.     for i in range(n):
   
8. 
   
9.         m+=3.0**np.gcd(n,i+1)
   
10. 
    
11.     m+=(2+n%2)*n*3**(n//2)
    
12. 
    
13.     return int(m//(2*n))
    
14. 
    
15. for n in range(1,31):
    
16. 
    
17.     print (n,count(n))

复制代码

northwolves

1 3
2 6
3 10
4 21
5 39
6 92
7 198
8 498
9 1219
10 3210
11 8418
12 22913
13 62415
14 173088
15 481598
16 1351983
17 3808083
18 10781954
19 30615354
20 87230157
21 249144711
22 713387076
23 2046856566
24 5884491500
25 16946569371
26 48883660146
27 141217160458
28 408519019449
29 1183289542815
30 3431533458328

northwolves

贴错代码了

markfang2050

要解决旋转相同或对称相同等的涂色问题，用burnside引理和polya定理解决高效。

northwolves

发现n>36之后结果与网站有差异，不知何故。
https://oeis.org/A027671

王守恩

198条独一无二的彩珠手链条码。
001=1111111
002=1111112
003=1111113
004=1111122
005=1111123
006=1111132
007=1111133
008=1111212
009=1111213
010=1111222
011=1111223
012=1111232
013=1111233
014=1111312
015=1111313
016=1111322
017=1111323
018=1111332
019=1111333
020=1112112
021=1112113
022=1112122
023=1112123
024=1112132
025=1112133
026=1112212
027=1112213
028=1112222
029=1112223
030=1112232
031=1112233
032=1112312
033=1112313
034=1112322
035=1112323
036=1112332
037=1112333
038=1113113
039=1113123
040=1113133
041=1113223
042=1113233
043=1113323
044=1113333
045=1121122
046=1121123
047=1121132
048=1121133
049=1121212
050=1121213
051=1121222
052=1121223
053=1121232
054=1121233
055=1121312
056=1121313
057=1121322
058=1121323
059=1121332
060=1121333
061=1122113
062=1122122
063=1122123
064=1122132
065=1122133
066=1122213
067=1122222
068=1122223
069=1122232
070=1122233
071=1122313
072=1122322
073=1122323
074=1122332
075=1122333
076=1123132
077=1123133
078=1123213
079=1123222
080=1123223
081=1123232
082=1123233
083=1123313
084=1123322
085=1123323
086=1123332
087=1123333
088=1131133
089=1131213
090=1131223
091=1131233
092=1131313
093=1131323
094=1131333
095=1132123
096=1132133
097=1132223
098=1132233
099=1132323
100=1132333
101=1133133
102=1133233
103=1133333
104=1212122
105=1212123
106=1212132
107=1212133
108=1212213
109=1212222
110=1212223
111=1212232
112=1212233
113=1212313
114=1212322
115=1212323
116=1212332
117=1212333
118=1213123
119=1213133
120=1213213
121=1213223
122=1213233
123=1213313
124=1213323
125=1213333
126=1221222
127=1221223
128=1221232
129=1221233
130=1221322
131=1221323
132=1221332
133=1221333
134=1222222
135=1222223
136=1222232
137=1222233
138=1222313
139=1222332
140=1222333
141=1223132
142=1223133
143=1223223
144=1223232
145=1223233
146=1223322
147=1223323
148=1223332
149=1223333
150=1231232
151=1231233
152=1231323
153=1231332
154=1231333
155=1232133
156=1232223
157=1232232
158=1232233
159=1232332
160=1232333
161=1233223
162=1233233
163=1233323
164=1233333
165=1313133
166=1313223
167=1313233
168=1322223
169=1322233
170=1322323
171=1322333
172=1323133
173=1323233
174=1323333
175=1331333
176=1332233
177=1332333
178=1333333
179=2222222
180=2222223
181=2222233
182=2222323
183=2222333
184=2223223
185=2223233
186=2223323
187=2223333
188=2232233
189=2232323
190=2232333
191=2233233
192=2233323
193=2233333
194=2323233
195=2323333
196=2332333
197=2333333
198=3333333

hujunhua

本坛讨论过这个问题，题目还是我给重新取的，所以还记得。
有一个初始数据表格，198在其中。
彩珠手串的配色计数