Permutation: Gibt die k-te Permutation zurück
Prakash N.
Ich weiß, dass es hier zum Beispiel eine O(n)zeitliche Komplexitätslösung für dieses Problem gibt .
Ich bin nur neugierig, warum mein naiver Ansatz O(2^n)in Python nicht funktioniert.
Algorithmus:
Ich finde die Permutationen nur rekursiv und wenn das kth-Element hinzugefügt wird, gebe ich es zurück. Ich erhalte jedoch das Rückgabeergebnis als None. Ich bin nicht sicher, warum Nonemeine Funktion zurückgegeben wird.
class Solution(object):
# Time complexity O(2 ^ n)
def getPermutation(self, n, k):
char_list = map(str, range(1, n + 1)) #convert to strin
used = [False] * len(char_list)
result = []
kthArray = self._getPermutation_helper(result, char_list, used, [], k)
print kthArray #kthArray is always None
def _getPermutation_helper(self, result, char_list, used, cur, k):
if len(char_list) == len(cur):
result.append(cur + [])
print len(result)
print cur
if len(result) == k:
print "cur in kth is {0}".format(cur)
return cur #cur is printed correctly but not returned
for i in range(len(char_list)):
if not used[i]:
cur.append(char_list[i])
used[i] = True
self._getPermutation_helper(result, char_list, used, cur, k)
# back track
used[i] = False
cur.remove(char_list[i])
def main():
pgm = Solution()
pgm.getPermutation(3, 6)
if __name__ == "__main__":
main()
Warum wird nicht der richtige Wert zurückgegeben?
IVlad
Weil Sie curzu einem vorherigen Aufruf derselben Funktion zurückkehren, von dem aus Sie ihn nicht weiter bis zum ersten Aufruf zurückgeben.
Sie müssen die gefundene Lösung bis zum ersten Aufruf weitergeben. Beispielsweise:
for i in range(len(char_list)):
if not used[i]:
cur.append(char_list[i])
used[i] = True
# Here we do a recursive call, which might find the answer we're looking for.
# So we save its return value and, if it's not None, we return it.
r = self._getPermutation_helper(result, char_list, used, cur, k)
if r is not None:
return r