回答編集履歴
1
コード追記
answer
CHANGED
|
@@ -1,2 +1,49 @@
|
|
|
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
|
-
数え方は[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)が参考になるかと。
|
|
2
|
+
数え方は[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)が参考になるかと。
|
|
3
|
+
```Python
|
|
4
|
+
# 「スワップ率」
|
|
5
|
+
def swap_rate(l):
|
|
6
|
+
|
|
7
|
+
# 必要スワップ回数
|
|
8
|
+
def swap_count(l):
|
|
9
|
+
count = 0
|
|
10
|
+
for j in range(len(l)):
|
|
11
|
+
for i in range(1, len(l)-j):
|
|
12
|
+
if l[i-1] > l[i]:
|
|
13
|
+
count += 1
|
|
14
|
+
l[i-1], l[i] = l[i], l[i-1]
|
|
15
|
+
return count
|
|
16
|
+
|
|
17
|
+
# 最悪スワップ回数
|
|
18
|
+
def max_count(l):
|
|
19
|
+
from collections import Counter
|
|
20
|
+
c = Counter(l)
|
|
21
|
+
assert len(c.values()) == 2 # ２種類のみで構成されたリスト
|
|
22
|
+
|
|
23
|
+
l_len = len(l)
|
|
24
|
+
max_cnt = 1
|
|
25
|
+
for v in c.values():
|
|
26
|
+
max_cnt *= l_len - v
|
|
27
|
+
|
|
28
|
+
# 検算
|
|
29
|
+
#l2 = sorted(l,reverse=True)
|
|
30
|
+
#assert swap_count(l2) == max_cnt
|
|
31
|
+
|
|
32
|
+
return max_cnt
|
|
33
|
+
|
|
34
|
+
swap_cnt = swap_count(l)
|
|
35
|
+
max_cnt = max_count(l)
|
|
36
|
+
return 1 - (swap_cnt/max_cnt)
|
|
37
|
+
|
|
38
|
+
|
|
39
|
+
for s in ['AAAABBBB','BBBBAAAA','AAABABBB','BAAABBBA','BAABAABB']:
|
|
40
|
+
r = swap_rate(list(s))
|
|
41
|
+
print(s,r)
|
|
42
|
+
"""
|
|
43
|
+
AAAABBBB 1.0
|
|
44
|
+
BBBBAAAA 0.0
|
|
45
|
+
AAABABBB 0.9375
|
|
46
|
+
BAAABBBA 0.5625
|
|
47
|
+
BAABAABB 0.625
|
|
48
|
+
"""
|
|
49
|
+
```
|