Python-Listenindex außerhalb des Bereichs in k-Tupel-Sortierung

Question

Ich möchte K-Tupel-Sortierung in kürzester Zeit implementieren, d. H. O (k (m + n)) Zeit.

Mein Code ist:

A = [(1,2,1),(2,3,1),(1,4,2),(2,2,2),(1,4,3),(3,2,1)] 
B = [[] for _ in range(5)] 

n = len(A[0]) - 1 

for j in (n,0,-1): 
    while(len(A) != 0): 
     a = A.pop(0) 
     B[a[j]].append(a) 
    for l in range(5): 
     A.append(B[l]) 

print(A) 

ich Fehler bei B[a[j]].append(a) als Index bin immer außerhalb des Bereichs liegt.

Answer 1

scheint, dass Sie etwas zu B [0] anhängen vergessen, starten Sie die Liste anhängen 1 und 2. Hier zu positionieren ist, was Sie

>>> A = [(1,2,1),(2,3,1),(1,4,2),(2,2,2),(1,4,3),(3,2,1)] 
>>> B = [[] for _ in range(5)] 
>>> 
>>> n = len(A[0]) - 1 
>>> 
>>> for j in (n,0,-1): 
...  print("j:%d" % j) 
...  while(len(A) != 0): 
...   a = A.pop(0) 
...   print("appending %s at position %s" % (str(a), str(a[j]))) 
...   B[a[j]].append(a) 
...  print("B:" + str(B)) 
...  for l in range(5): 
...   print("l:%d" %l) 
...   A.append(B[l]) 
...  print("A:" + str(A)) 
... 
j:2 
appending (1, 2, 1) at position 1 
appending (2, 3, 1) at position 1 
appending (1, 4, 2) at position 2 
appending (2, 2, 2) at position 2 
appending (1, 4, 3) at position 3 
appending (3, 2, 1) at position 1 
B:[[], [(1, 2, 1), (2, 3, 1), (3, 2, 1)], [(1, 4, 2), (2, 2, 2)], [(1, 4, 3)], []] 
l:0 
l:1 
l:2 
l:3 
l:4 
A:[[], [(1, 2, 1), (2, 3, 1), (3, 2, 1)], [(1, 4, 2), (2, 2, 2)], [(1, 4, 3)], []] 
j:0 
Traceback (most recent call last): 
    File "<stdin>", line 5, in <module> 
IndexError: list index out of range 

Answer 2

tun Ich verstehe, dass Sie eine Radixsort zu implementieren versuchen .

Die Linie A.append(B[l]) ist falsch, weil Sie die Liste B[l] als das letzte Element der Liste A statt am Ende der Liste A die Elemente B[l] Hinzufügen hinzufügen. Dies bewirkt, dass a[j] in der zweiten Iteration der for-Schleife IndexError als a = [] auslöst.

Dann sollten Sie Ihre äußere for-Schleife range(n, -1, -1) verwenden, die [2, 1, 0] wenn n==2 (die documentation here sehen) zurückgibt.

Auch B muss für jede Iteration der äußeren Schleife leer sein.

A = [(1,2,1),(2,3,1),(1,4,2),(2,2,2),(1,4,3),(3,2,1)] 

n = len(A[0]) - 1 

for i in range(n, -1, -1): # range(start, stop, step) 
    B = [[] for _ in range(5)] # B needs to be empty for each iteration 
    while(len(A)): 
     a = A.pop(0) 
     B[a[i]].append(a) 

    for j in range(5): 
     A += B[j] # Adding elements of B[j] to the end of A 

print(A)