回答編集履歴
1
コード追記
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
|
+
```
|