7

ここではリアルタイムでポリゴン データを扱っていますが、問題は非常に単純です。何千ものポリゴン インデックス (整数) のセットを含む巨大なリストがあり、そのリストをできるだけ「高速」に単純化して、「接続された」インデックスのセットのリストにする必要があります。つまり、別のセットにもある整数を含むセットは、結果で 1 つのセットになります。セットとグラフなどを含むいくつかの可能な解決策を読みました。私が求めているのは、ある程度の共通性を持つセットの最終的なリストです。

ここでは多くのデータを扱っていますが、簡単にするためにサンプル データをいくつか示します。

setA = set([0,1,2])
setB = set([6,7,8,9])
setC = set([4,5,6])
setD = set([3,4,5,0])
setE = set([10,11,12])
setF = set([11,13,14,15])
setG = set([16,17,18,19])

listOfSets = [setA,setB,setC,setD,setE,setF,setG]

この場合、順序は関係ありませんが、次のような結果のリストを求めています。

connectedFacesListOfSets = [ set([0,1,2,3,4,5,6,7,8,9]), set([10,11,12,13,14,15]), set([16, 17,18,19])]

同様のソリューションを探しましたが、投票数が最も多かったソリューションは、大規模なテスト データに対して誤った結果をもたらしました。

共通の要素を共有するリストを統合する

4

5 に答える 5

4

十分に大きなセットがないとパフォーマンスを判断するのは難しいですが、ここから始めるための基本的なコードをいくつか示します。

while True:
    merged_one = False
    supersets = [listOfSets[0]]

    for s in listOfSets[1:]:
        in_super_set = False
        for ss in supersets:
            if s & ss:
               ss |= s
               merged_one = True
               in_super_set = True
               break

        if not in_super_set:
            supersets.append(s)

    print supersets
    if not merged_one:
        break

    listOfSets = supersets

これは、提供されたデータに対して3回の反復で機能します。そして、出力は次のとおりです。

[set([0, 1, 2, 3, 4, 5]), set([4, 5, 6, 7, 8, 9]), set([10, 11, 12, 13, 14, 15]), set([16, 17, 18, 19])]
[set([0, 1, 2, 3, 4, 5, 6, 7, 8, 9]), set([10, 11, 12, 13, 14, 15]), set([16, 17, 18, 19])]
[set([0, 1, 2, 3, 4, 5, 6, 7, 8, 9]), set([10, 11, 12, 13, 14, 15]), set([16, 17, 18, 19])]
于 2011-05-26T20:46:56.213 に答える
2

これは共用体検索の問題です。

私はまだ使っていませんが、この Python コードは私には良さそうです。

http://code.activestate.com/recipes/577225-union-find/

于 2011-05-26T20:14:23.033 に答える
1

めちゃくちゃな大文字を許してください（自動修正...）：

# the results cotainer
Connected = set()

sets = # some list of sets

# convert the sets to frozensets (which are hashable and can be added to sets themselves)
Sets = map(frozenset, sets)

for s1 in sets:
    Res = copy.copy(s1)
    For s2 in sets:
        If s1 & s2:
            Res = res | s2
    Connected.add(res)
于 2011-05-26T20:52:28.217 に答える
0

だから..私はそれを得たと思います。ぐちゃぐちゃですが、わかりました。これが私がしたことです：

def connected_valid(li):
    for i, l in enumerate(li):
        for j, k in enumerate(li):
            if i != j and contains(l,k):
                return False
    return True

def contains(set1, set2):
    for s in set1:
        if s in set2:
            return True
    return False

def combine(set1, set2):
    set2 |= set1
    return set2

def connect_sets(li):
    while not connected_valid(li):
        s1 = li.pop(0)
        s2 = li[0]
        if contains(s1, s2):
            li[0] = combine(s1,s2)
        else:
            li.append(s1)
    return li

次に、メイン関数で次のようにします。

setA = set([0,1,2])
setB = set([6,7,8,9])
setC = set([4,5,6])
setD = set([3,4,5,0])
setE = set([10,11,12])
setF = set([11,13,14,15])
setG = set([16,17,18,19])

connected_sets = connect_sets([setA,setB,setC,setD,setE,setF,setG,])

実行した後、次の出力が得られました

print connected_sets
[set([0,1,2,3,4,5,6,7,8,9]), set([10,11,12,13,14,15]), set([16,17,18,19])]

それがあなたが探しているものであることを願っています。

編集: セットをランダムに生成するコードを追加:

# Creates a list of 4000 sets with a random number of values ranging from 0 to 20000
sets = []
ma = 0
mi = 21000
for x in range(4000):
    rand_num = sample(range(20),1)[0]
    tmp_set_li = sample(range(20000), rand_num)
    sets.append(set(tmp_set_li))

必要に応じて、最後の 3 行を 1 行にまとめることができます。

于 2011-05-26T21:12:47.780 に答える
0

私は何か違うことをしようとしました: このアルゴリズムは、セットごとに 1 回、要素ごとに 1 回ループします。

# Our test sets
setA = set([0,1,2])
setB = set([6,7,8,9])
setC = set([4,5,6])
setD = set([3,4,5,0])
setE = set([10,11,12])
setF = set([11,13,14,15])
setG = set([16,17,18,19])

list_of_sets = [setA,setB,setC,setD,setE,setF,setG]

# We will use a map to store our new merged sets.
# This map will work as an reference abstraction, so it will
# map set ids to the set or to other set id.
# This map may have an indirection level greater than 1
merged_sets = {}

# We will also use a map between indexes and set ids.
index_to_id = {}

# Given a set id, returns an equivalent set id that refers directly
# to a set in the merged_sets map
def resolve_id(id):
    if not isinstance(id, (int, long)):
        return None
    while isinstance(merged_sets[id], (int, long)):
        id = merged_sets[id]
    return id


# Points the informed set to the destination id
def link_id(id_source, id_destination):
    point_to = merged_sets[id_source]
    merged_sets[id_source] = id_destination
    if isinstance(point_to, (int, long)):
        link_id(point_to, id_destination)


empty_set_found = False
# For each set
for current_set_id, current_set in enumerate(list_of_sets):
    if len(current_set) == 0 and empty_set_found:
        continue
    if len(current_set) == 0:
        empty_set_found = True
    # Create a set id for the set and place it on the merged sets map
    merged_sets[current_set_id] = current_set
    # For each index in the current set
    possibly_merged_current_set = current_set
    for index in current_set:
        # See if the index is free, i.e., has not been assigned to any set id
        if index not in index_to_id:
            # If it is free, then assign the set id to the index
            index_to_id[index] = current_set_id
            # ... and then go to the next index
        else:
            # If it is not free, then we may need to merge the sets
            # Find out to which set we need to merge the current one,
            # ... dereferencing if necessary
            id_to_merge = resolve_id(index_to_id[index])
            # First we check to see if the assignment is to the current set or not
            if id_to_merge == resolve_id(merged_sets[current_set_id]):
                continue
            # Merge the current set to the one found
            print 'Merging %d with %d' % (current_set_id, id_to_merge)
            merged_sets[id_to_merge] |= possibly_merged_current_set
            possibly_merged_current_set = merged_sets[id_to_merge]
            # Map the current set id to the set id of the merged set
            link_id(current_set_id, id_to_merge)
# Return all the sets in the merged sets map (ignore the references)
print [x for x in merged_sets.itervalues() if not isinstance(x, (int, long))]

それは印刷します：

Merging 2 with 1
Merging 3 with 0
Merging 3 with 1
Merging 5 with 4
[set([0, 1, 2, 3, 4, 5, 6, 7, 8, 9]), set([10, 11, 12, 13, 14, 15]), set([16, 17, 18, 19])]
于 2011-05-27T17:11:47.597 に答える