0

タイトルで問題を説明する方法がわからない。

ここに問題があります：

4つのグループがあると仮定します。

(a, b, c, d)
(e, f)
(g, h, i)
(j, k, l, m, n)

これで、4つの要素のタプルが与えられました。たとえば(a, e, h, m)、どちらも1つのグループからのものではないため、Trueを返します。が与えられた場合(a, b, e, g)、それa, bは1つのグループからのものであり、Falseを返します。

次に、これが私の現在のアイデアです。各要素にグループ番号で始まるIDを指定し、重複をテストします。

g1 = ['1a', '1b', '1c', '1d']
g2 = ['2e', '2f']
g3 = ['3g', '3h', '3i']
g4 = ['4j', '4k', '4l', '4m', '4n']


def test(elements):
    if len(elements) != 4:
        return False

    stack = []
    for e in elements:
        mark = e[:1]
        if mark in stack:
            return False
        stack.append(mark)

    ga = set(g1 + g2 + g3 + g4)
    return set(elements).issubset(ga)


print test(('1a', '1b', '2e', '3g'))
print test(('1a', '2e', '3g', '4m'))

しかし、文字列比較はあまり洗練されたソリューションではないと思います。これは別のより高速なアルゴリズムで実行できますか？

4

2 に答える 2

4

すべての要素がハッシュ可能である場合、私は：を使用しset.intersectionます

g1 = set(['1a', '1b', '1c', '1d'])
g2 = set(['2e', '2f'])
g3 = set(['3g', '3h', '3i'])
g4 = set(['4j', '4k', '4l', '4m', '4n'])

sets = [g1,g2,g3,g4]
test_this = ['1a','2e','3g','4j']

all(len(s.intersection(test_this)) <= 1 for s in sets)

または、g1、g2のタイプを変更したくない場合は、次のタイプを変更できますtest_this。

g1 = ['1a', '1b', '1c', '1d']
g2 = ['2e', '2f']
g3 = ['3g', '3h', '3i']
g4 = ['4j', '4k', '4l', '4m', '4n']
lists = [g1,g2,g3,g4]
test_this = set(['1a','2e','3g','4j'])

all( len(test_this.intersection(lst)) <= 1 for lst in lists )

ここでの美しさは、all短絡するのに十分スマートであるということです。ジェネレータ式を使用しているため、すべての交点を事前に計算する必要はありません。Pythonは、以前のすべての交差点の長さが1以下である限り、交差点の計算を続行します。

于 2012-11-15T05:33:09.877 に答える
2

mgilsonと同じように、インタプリタで遊んでいるだけですが、チェックする必要はありませんlen()。既存のset（）はTrueと評価されます。

>>> g1 = ['1a', '1b', '1c', '1d']
>>> g2 = ['2e', '2f']
>>> g3 = ['3g', '3h', '3i']
>>> g4 = ['4j', '4k', '4l', '4m', '4n']
>>>
>>> groups = (g1, g2, g3, g4)
>>> t1 = ('1a', '1b', '2e', '3g')
>>> t2 = ('1a', '2e', '3g', '4m')
>>>
>>> all(set(t2).intersection(g) for g in groups)
True
>>> all(set(t1).intersection(g) for g in groups)
False
>>>
于 2012-11-15T05:38:42.327 に答える