Vinnaren i pepparkakshustävlingen!
  1. Dator och IT
  2. Systemutveckling
  3. Python

Gruppera massor med element i ett par listor med hjälp utav itertools.combinations

Svara
2016-06-11, 18:33
  #1
Spader
Medlem
Spaders avatar
Jag har en lista (elementList) med olika objekt som har lite olika properties, bland annat ID och position (x,y). Jag vill loopa igenom denna lista och kolla varje element mot alla andra element, och köra en funktion (inRangeOf) och utifrån detta skapa en lista med kluster: alltså en lista över element som hör ihop. Sen vill jag självklart inte jämföra två element mer än en gång, så har "a" checkats mot "b" så ska inte "b" senare checka mot "a".

Det första försöket såg ut så här:
Kod: 
# Check all elements against all other elements in elementList, group together as clusters
clusterList = []
for p in elementList:
    cluster = []
    cluster.append(p)
    for o in elementList:
        if o == p: continue
        if p.inRangeOf(o, rangeValue): # rangeValue är ett rörligt tröskelvärde bara
            cluster.append(o)

    for v in cluster:
        elementList.remove(v)
        clusterList.append(cluster)

# Check what clusters we have
for item in clusterList: print item
Den koden funkar men är dock inte felfri: problem uppstår då jag raderar från listan elementList samtidigt som jag itererar över den - vilket fuckar indexordningen (ibland så blir det att jag "hoppar över" ett index, säg 2, och att index 2 då inte kollar mot alla andra värden.

Jag kollade runt lite och insåg att det troligen är bättre att bara köra med itertools.combinations för att kolla alla element mot varandra. Exempel på användning utav itertools.combinations
Kod: 
import itertools
myList = ["a", "b", "c", "d", "e", "f", "g", "h"]
for x,y in itertools.combinations(myList, 2):
    print x,y
Problemet här är att jag inte vet hur jag ska skapa en lista över klustren. Säg att följande element är nära varandra: a och b, c och d, e och f, g och h - då vill jag att min lista (clusterList) i slutändan innehåller listor i stil med:
[["a", "b"], ["c", "d"], ["e", "f"], ["g", "h"]]

Jag har setat för länge med det här problemet nu att jag har börjat få mental härdsmälta. Det är säkert något uppenbart jag missar.
__________________
Senast redigerad av Spader 2016-06-11 kl. 19:25.
Citera
2016-06-11, 19:58
  #2
enowen
Medlem
enowens avatar
Citat:
Ursprungligen postat av Spader
Jag har en lista (elementList) med olika objekt som har lite olika properties, bland annat ID och position (x,y). Jag vill loopa igenom denna lista och kolla varje element mot alla andra element, och köra en funktion (inRangeOf) och utifrån detta skapa en lista med kluster: alltså en lista över element som hör ihop. Sen vill jag självklart inte jämföra två element mer än en gång, så har "a" checkats mot "b" så ska inte "b" senare checka mot "a".

Det första försöket såg ut så här:
Kod: 
# Check all elements against all other elements in elementList, group together as clusters
clusterList = []
for p in elementList:
    cluster = []
    cluster.append(p)
    for o in elementList:
        if o == p: continue
        if p.inRangeOf(o, rangeValue): # rangeValue är ett rörligt tröskelvärde bara
            cluster.append(o)

    for v in cluster:
        elementList.remove(v)
        clusterList.append(cluster)

# Check what clusters we have
for item in clusterList: print item
Den koden funkar men är dock inte felfri: problem uppstår då jag raderar från listan elementList samtidigt som jag itererar över den - vilket fuckar indexordningen (ibland så blir det att jag "hoppar över" ett index, säg 2, och att index 2 då inte kollar mot alla andra värden.

Jag kollade runt lite och insåg att det troligen är bättre att bara köra med itertools.combinations för att kolla alla element mot varandra. Exempel på användning utav itertools.combinations
Kod: 
import itertools
myList = ["a", "b", "c", "d", "e", "f", "g", "h"]
for x,y in itertools.combinations(myList, 2):
    print x,y
Problemet här är att jag inte vet hur jag ska skapa en lista över klustren. Säg att följande element är nära varandra: a och b, c och d, e och f, g och h - då vill jag att min lista (clusterList) i slutändan innehåller listor i stil med:
[["a", "b"], ["c", "d"], ["e", "f"], ["g", "h"]]

Jag har setat för länge med det här problemet nu att jag har börjat få mental härdsmälta. Det är säkert något uppenbart jag missar.

Försöker simulera det du ville ha gjort, ett alternativ är att markera objekten du ska ta bort "for deletion" och sedan ta bort dem. Vet inte riktigt hur ditt exempel används men jag skrev någonting här, kanske hjälper:

Kod:
from random import randint

class soldier(object):
    def __init__(self, soldierId, x, y):
        self._id = soldierId
        self._x = x
        self._y = y
        self._marked_for_deletion = False

    def getId(self):
        return self._id

    def getPosition(self):
        return self._x, self._y

    def markForDeletion(self):
        self._marked_for_deletion = True

    def isMarkedForDeletion(self):
        return self._marked_for_deletion

    def inRangeOf(self, obj, rangeValue):
        posX, posY = obj.getPosition()
        if abs(posX-self._x) <= rangeValue and abs(posY-self._y) <= rangeValue:
            return True
        else:
            return False

def create_soldiers(num):
    myList = []
    for i in range(num):
        myList.append(soldier(randint(1000,9999), randint(0, 19), randint(0, 19)))
    return myList

def create_cluster(elementList):
    rangeValue = 2
    clusterList = []
    for p in elementList:
        cluster = [p]
        cluster = [o for o in elementList if o != p and p.inRangeOf(o, rangeValue)]
        for v in cluster:
            v.markForDeletion()
            clusterList.append(cluster)

    elementList = [p for p in elementList if not p.isMarkedForDeletion()]
    return clusterList, elementList

def main():
    # create some soldiers
    soldierList = create_soldiers(5)
    clusterList, newSoldierList = create_cluster(soldierList)
    for l in clusterList:
        for s in l:
            posX, posY = s.getPosition()
            print("id =", s.getId(), "x =", posX, "y =", posY)

if __name__ == "__main__":
    main() 

Alternativt så kan du skriva:

Kod:
for p in list(elementList): 
för att iterera över en kopia av din elementList om du ska ta bort saker från den, så slipper du oroa dig för det.
Citera
2016-06-11, 22:28
  #3
Spader
Medlem
Spaders avatar
Tack för svaret!
Det blev dock en annan lösning i slutändan:

Kod: 
# Generate list of all UV point pairs that needs to be compared
compareList = [x for x in itertools.combinations(pointList, 2)]
clusterList = []

# Compare all points against all other points (by distance) - Create list of point clusters
for p in pointList:
    if any(p in i for i in clusterList): continue # Is the current point an element of any sublist in clusterList?
    cluster = []
    cluster.append(p)

    for pair in compareList:
        if pair[0] != cluster[0]: continue # Skip unnecessary comparisons
        if pair[0].inRangeOf(pair[1], matchTol): cluster.append(pair[1]) # Append to cluster if point is in range

    clusterList.append(cluster) # Add cluster of points to cluster list

print("TEST")
for item in clusterList:
    print item
På detta vis så får jag minsta möjliga antalet sökningar, och mina element grupperas i grupper om kluster.
Citera
Svara

Stöd Flashback

Flashback finansieras genom donationer från våra medlemmar och besökare. Det är med hjälp av dig vi kan fortsätta erbjuda en fri samhällsdebatt. Tack för ditt stöd!

Stöd Flashback