3

rodsとのタプルで構成されるリストがlengthありpositionます。 positionは、特定の に対して常に一意ですlength。position最も頻度の高いロッドの長さを見つけてから、 (最も頻度の高いロッドを含む) 隣接するすべての一意のロッドの出現回数の合計を見つけたいと考えています。内訳：

  • まず、最も頻度の高いロッドを見つけたいと思いますlength。
  • 次に、いくつかの基準 (この例では +-1) によって隣接している他のすべてのロッドを含めたいと思いますが、それらがlength一意の位置を持っている場合のみ - まだ考慮されていません (元のグループの「最も頻繁な」ロッドによって、または、隣接する基準を満たすことによってこのグループに追加された「新しいロッド」によって)。
  • そして、この新しい総頻度を見つけます。

セットを並べ替えて使用することにより、次の方法でこれを達成できますが、おそらくより良い解決策があります。

import itertools
#tuples of (length, position)
rods = [(18, 21), (17, 2), (15, 3), (14, 21), (14, 5), (13, 6), (13, 7),
        (13, 8), (13, 9), (13, 10), (13, 11), (13, 12), (13, 13), (13, 14),
        (13, 15), (13, 16), (13, 17), (13, 18), (13, 19), (13, 20), (13, 21),
        (13, 22), (13, 23), (13, 24), (13, 25), (13, 26), (12, 5), (12, 21),
        (12, 2)]

lengths = [length for length, position in rods]

#gives tuples of lengths and their frequencies:
length_freq = (sorted([(k,len(list(j))) for k,j in itertools.groupby(sorted(lengths))],
               key=lambda x: x[1],reverse=1))
best_length = length_freq[0][0]

#cumulative frequency of rods near best_length, with unique position:
tally = (len(set((best_length,v) for j,v in rods 
         if best_length - 1 <= j <=best_length + 1)))

print length_freq
#output:
#[(13, 21), (12, 3), (14, 2), (15, 1), (17, 1), (18, 1)]
print tally
#output:
#23

注23は、このテスト データの正解です。の両方のロッドは、 (位置、および) のlength= 14ロッドによって占められている点にも配置されています。また、 for にも重複があります。length=15215position=21lengths 13 and 12

4

2 に答える 2

2

少し圧縮しすぎると、全体的に合理的なソリューションだと思います。私の主な提案は、それをもう少し分解することです。groupbyまた、ここで使用する代わりに、Counter可能なdefaultdict場合は a、そうでない場合は a を使用することをお勧めします。groupby事前にソートされた素材に対する遅延操作用です。事前にソートされておらず、遅延する必要がない場合は、おそらく使用しないでください。

Nolen Royalydefaultdictは に基づくソリューションを提供しているのでCounter、ここで使用しますが、ドロップインの代替品については以下を参照してください。結果は O(n) アルゴリズムです。あなたの並べ替えは O(n log n) なので、これはわずかな改善です。

import collections

#tuples of (length, position)
rods = [(18, 21), (17, 2), (15, 3), (14, 21), (14, 5), (13, 6), (13, 7),
        (13, 8), (13, 9), (13, 10), (13, 11), (13, 12), (13, 13), (13, 14),
        (13, 15), (13, 16), (13, 17), (13, 18), (13, 19), (13, 20), (13, 21),
        (13, 22), (13, 23), (13, 24), (13, 25), (13, 26), (12, 5), (12, 21),
        (12, 2)]

lengths = (length for length, position in rods)
length_freq = collections.Counter(lengths)
((best_length, _),) = length_freq.most_common(1)
print best_length

#cumulative frequency of rods near best_length, with unique position:
rod_filter = ((l, p) for l, p in rods if best_length - 1 <= l <= best_length + 1)
tally = len(set((best_length, p) for l, p in rod_filter))

print length_freq
print tally

を使用できないためCounter、完全を期すために、代替手段を次に示します。これは、次の 2 行のドロップイン置換です。

length_freq = collections.Counter(lengths)
((best_length, _),) = length_freq.most_common(1)

それらを次のように置き換えるだけです。

length_freq = collections.defaultdict(int)
for l in lengths:
    length_freq[l] += 1
best_length = max(length_freq, key=length_freq.get)

また、以前のコードにエラーがあったことにも注意してください。今は修正されています。

于 2012-04-19T14:25:59.240 に答える
1

これは、私にとってかなり合理的と思われる非常に簡単な方法です。

>>> from collections import defaultdict
>>> rods = [(18, 21), (17, 2), (15, 3), (14, 21), (14, 5), (13, 6), (13, 7),
...         (13, 8), (13, 9), (13, 10), (13, 11), (13, 12), (13, 13), (13, 14),
...         (13, 15), (13, 16), (13, 17), (13, 18), (13, 19), (13, 20), (13, 21),
...         (13, 22), (13, 23), (13, 24), (13, 25), (13, 26), (12, 5), (12, 21),
...         (12, 2)]
>>> neighbor_cutoff = 1
>>> length_to_count = defaultdict(int)
>>> neighbors_for_length = defaultdict(set)
>>> for rod in rods:
...     length_to_count[rod[0]] += 1
...     neighbors_for_length[rod[0]].add(rod[1])
...     for i in range(1, neighbor_cutoff+1):
...         neighbors_for_length[rod[0]-i].add(rod[1])
...         neighbors_for_length[rod[0]+i].add(rod[1])
... 
>>> sorted([(length, length_to_count[length]) for length in length_to_count], key=lambda x: x[1], reverse=True)
[(13, 21), (12, 3), (14, 2), (15, 1), (17, 1), (18, 1)]
>>> [(length, len(neighbors_for_length[length])) for length in neighbors_for_length]
[(11, 3), (12, 23), (13, 23), (14, 23), (15, 3), (16, 2), (17, 2), (18, 2), (19, 1)]
>>> sorted(_, key=lambda x: x[1], reverse=True)
[(12, 23), (13, 23), (14, 23), (11, 3), (15, 3), (16, 2), (17, 2), (18, 2), (19, 1)]
>>> neighbors_for_length
defaultdict(<type 'set'>, {11: set([2, 5, 21]), 12: set([2, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26]), 
13: set([2, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26]), 
14: set([3, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26]),
15: set([3, 21, 5]), 16: set([2, 3]), 17: set([2, 21]), 18: set([2, 21]), 19: set([21])})
于 2012-04-19T14:20:37.660 に答える