计算一个图形中的三角形数目

greatleaf

微信朋友圈的一个游戏，数三角形的数目。自己用Python了一个小程序来处理了一下。
代码段：
      triangle_counter.py

1. #!/usr/bin/python
   
2. 
   
3. """
   
4. ---------------------------------------------------------------------------------------------------
   
5. 2015.07.23  Grey
   
6. ***************************************************************************************************
   
7. Counter all the triangles in a picture
   
8. ---------------------------------------------------------------------------------------------------
   
9. """
   
10. 
    
11. import itertools,string
    
12. 
    
13. def CounterTriangle():
    
14.     print "All the triangles we can find in the picture are as follows:"
    
15.     triangle_number    = 0
    
16.     sides_match_list   = ['abh','acgi','adfj','aek','bcde','efgh','hijk']
    
17.     dot_list           = []
    
18.     i = 0
    
19.     while i < 26:
    
20.         dot_list.append(string.lowercase[i])
    
21.         if string.lowercase[i] == 'k':
    
22.             break
    
23.         else:
    
24.             i += 1
    
25.     for each_combination in itertools.combinations(dot_list,3):
    
26.         triangle_flag = True
    
27.         for each_dot_combination in itertools.combinations(each_combination,2):
    
28.             for each_side in sides_match_list:
    
29.                 if each_dot_combination[0] in each_side and each_dot_combination[1] in each_side:
    
30.                     triangle_flag = True
    
31.                     break
    
32.                 else:
    
33.                     triangle_flag = False
    
34.             else:
    
35.                 triangle_flag = False
    
36.                 break
    
37.         line_flag = False
    
38.         for each_side in sides_match_list:
    
39.             if each_combination[0] in each_side and each_combination[1] in each_side and each_combination[2] in each_side:
    
40.                 line_flag = True
    
41.         if triangle_flag == True and line_flag == False:
    
42.             triangle_number += 1
    
43.             print "%d : %s" % (triangle_number,each_combination)
    
44.     print "The number of triangles in the picture is : %d" % triangle_number
    
45. 
    
46. CounterTriangle()
    
47.         

复制代码

haooooaaa

学习了, 没想到还可以这样折腾.

substr函数

回复 2# haooooaaa


想请教大神，能否说说思路， 或者原理； 非常感谢！

haooooaaa

回复 3# substr函数


    也尝试折腾了一下.

1. #!/usr/bin/env python
   
2. import itertools
   
3. 
   
4. a = ['abh','acgi','adfj','aek','bcde','efgh','hijk']
   
5. a = [ set(i) for i in a ]
   
6. 
   
7. def CounterTri():
   
8.     k = []
   
9.     for x in itertools.combinations(a, 3):
   
10.         o, p, q = x[0] & x[1], x[1] & x[2], x[2] & x[0]
    
11.         if bool(o) and bool(p) and bool(q) and o != p != q:
    
12.             k.append(list(o | p | q))
    
13.             
    
14.     print "Triangle Counter is %s" % len(k)
    
15.    
    
16.     for i in k:
    
17.         print i
    
18.    
    
19. CounterTri()

复制代码

1. $ python ttt.py
   
2. Triangle Counter is 24
   
3. ['a', 'c', 'b']
   
4. ['a', 'h', 'g']
   
5. ['a', 'i', 'h']
   
6. ['a', 'b', 'd']
   
7. ['a', 'h', 'f']
   
8. ['a', 'h', 'j']
   
9. ['a', 'b', 'e']
   
10. ['a', 'h', 'e']
    
11. ['a', 'h', 'k']
    
12. ['h', 'b', 'e']
    
13. ['a', 'c', 'd']
    
14. ['a', 'g', 'f']
    
15. ['a', 'i', 'j']
    
16. ['a', 'c', 'e']
    
17. ['a', 'e', 'g']
    
18. ['a', 'i', 'k']
    
19. ['c', 'e', 'g']
    
20. ['i', 'h', 'g']
    
21. ['a', 'e', 'd']
    
22. ['a', 'e', 'f']
    
23. ['a', 'k', 'j']
    
24. ['e', 'd', 'f']
    
25. ['h', 'j', 'f']
    
26. ['h', 'k', 'e']
    

复制代码

substr函数

回复 4# haooooaaa


我是小白〜大神，能否说说思路， 或者原理

haooooaaa

回复 5# substr函数


['abh','acgi','adfj','aek','bcde','efgh','hijk']

相就的点的元素集体如上.

而任意两线的交点只有一个. ==> 这个可以用 交集去得到.

然后三角形为三个点.

用 itertools的组合方法 得到 任意3个点元素集的 组合.

再两两取交集. 得到 三个点.

substr函数

回复 6# haooooaaa


感谢大神！
！懂了

substr函数

     也尝试一下

1. ('a', 'c', 'b')
   
2. ('a', 'h', 'g')
   
3. ('a', 'i', 'h')
   
4. ('a', 'b', 'd')
   
5. ('a', 'h', 'f')
   
6. ('a', 'h', 'j')
   
7. ('a', 'b', 'e')
   
8. ('a', 'h', 'e')
   
9. ('a', 'h', 'k')
   
10. ('h', 'b', 'e')
    
11. ('a', 'c', 'd')
    
12. ('a', 'g', 'f')
    
13. ('a', 'i', 'j')
    
14. ('a', 'c', 'e')
    
15. ('a', 'e', 'g')
    
16. ('a', 'i', 'k')
    
17. ('c', 'e', 'g')
    
18. ('i', 'h', 'g')
    
19. ('a', 'e', 'd')
    
20. ('a', 'e', 'f')
    
21. ('a', 'k', 'j')
    
22. ('e', 'd', 'f')
    
23. ('h', 'j', 'f')
    
24. ('h', 'k', 'e')
    
25. 
    
26. TOTAL TRIANGELS IS 24
    

复制代码

1. #!/usr/bin/python2
   
2. 
   
3. from itertools import combinations as COMBINA
   
4. 
   
5. TRIANGLE = ['abh', 'acgi', 'adfj', 'aek', 'bcde', 'efgh', 'hijk']
   
6. TRIANGLE = [set(i) for i in TRIANGLE]
   
7. 
   
8. 
   
9. def COUNT(TRIANGLE):
   
10.     COUNT = 0
    
11.     for A, B, C in COMBINA(TRIANGLE, 3):
    
12.         POINTS = set(A & B | B & C | C & A)
    
13.         if len(POINTS) == 3: print tuple(POINTS); COUNT += 1
    
14.     print "\nTOTAL TRIANGELS IS %d" % COUNT
    
15. 
    
16. 
    
17. COUNT(TRIANGLE)
    

复制代码

substr函数

回复 1# greatleaf


这个微信朋友圈的代码太差劲了。

It sucks 烂透了；

substr函数

LZ？不知道微信朋友圈 学python是自学还是参加培训？