回答編集履歴

1

コード追記

2019/02/11 07:10

投稿

can110
can110

スコア38233

test CHANGED
@@ -1,3 +1,97 @@
1
1
  [バブルソート](https://ja.wikipedia.org/wiki/%E3%83%90%E3%83%96%E3%83%AB%E3%82%BD%E3%83%BC%E3%83%88)してスワップした回数を数えるのはいかがでしょうか(大きいほど正答率は低い)。
2
2
 
3
3
  数え方は[How to count number of swaps in a bubble sort?](https://stackoverflow.com/questions/29288367/how-to-count-number-of-swaps-in-a-bubble-sort)が参考になるかと。
4
+
5
+ ```Python
6
+
7
+ # 「スワップ率」
8
+
9
+ def swap_rate(l):
10
+
11
+
12
+
13
+ # 必要スワップ回数
14
+
15
+ def swap_count(l):
16
+
17
+ count = 0
18
+
19
+ for j in range(len(l)):
20
+
21
+ for i in range(1, len(l)-j):
22
+
23
+ if l[i-1] > l[i]:
24
+
25
+ count += 1
26
+
27
+ l[i-1], l[i] = l[i], l[i-1]
28
+
29
+ return count
30
+
31
+
32
+
33
+ # 最悪スワップ回数
34
+
35
+ def max_count(l):
36
+
37
+ from collections import Counter
38
+
39
+ c = Counter(l)
40
+
41
+ assert len(c.values()) == 2 # 2種類のみで構成されたリスト
42
+
43
+
44
+
45
+ l_len = len(l)
46
+
47
+ max_cnt = 1
48
+
49
+ for v in c.values():
50
+
51
+ max_cnt *= l_len - v
52
+
53
+
54
+
55
+ # 検算
56
+
57
+ #l2 = sorted(l,reverse=True)
58
+
59
+ #assert swap_count(l2) == max_cnt
60
+
61
+
62
+
63
+ return max_cnt
64
+
65
+
66
+
67
+ swap_cnt = swap_count(l)
68
+
69
+ max_cnt = max_count(l)
70
+
71
+ return 1 - (swap_cnt/max_cnt)
72
+
73
+
74
+
75
+
76
+
77
+ for s in ['AAAABBBB','BBBBAAAA','AAABABBB','BAAABBBA','BAABAABB']:
78
+
79
+ r = swap_rate(list(s))
80
+
81
+ print(s,r)
82
+
83
+ """
84
+
85
+ AAAABBBB 1.0
86
+
87
+ BBBBAAAA 0.0
88
+
89
+ AAABABBB 0.9375
90
+
91
+ BAAABBBA 0.5625
92
+
93
+ BAABAABB 0.625
94
+
95
+ """
96
+
97
+ ```