Python Forum
Storing Minimum List of values from a recursive function
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Storing Minimum List of values from a recursive function
#1
Hello,

I need to implement a function that accepts an input of a list and return the sorted version of this list after generating all possible permutations
e.g.:

3, 7, 1
its permutations are:
1, 3, 7
1, 7, 3
3, 7, 1
3, 1, 7
7, 1, 3
7, 3, 1

I managed to write a recursive function to generate these permutations but I want this function to output (1, 3, 7) only how can I do this?

arr = [7, 1, 3]
sortedList = arr
def permutationSort(arr, flag, p, ):
    if len(arr) == len(p):
        print(p) #here I can see that I can get all permutations
        global sortedList
        if p < sortedList:
            sortedList = p


    for i in range(len(arr)):
        if flag[i] == 1:
            continue
        else:
            flag[i] = 1
            p.append(arr[i])
            permutationSort(arr, flag, p)
            p.pop()
            flag[i] = 0

permutationSort(arr, [0]*(len(arr)), [])
print(sortedList) #this is not the correct answer
Reply
#2
You haven't written a function to generate the permutations. You've written a function to show the permutations. The function returns nothing (or rather, None). The reason you are getting an empty list at the end is that you are assigning p to sortedList. But p is a list, which is a mutable data type. So when you change p, you change sortedList as well. Then you go on to do a bunch of appends and pops to p, which is where I'm guessing it gets emptied.

Don't use global. Use the return statement to return values from your functions. Your recursive function should return a list of permutations. When it gets to the bottom of the recursion, it should return a list containing the permutation it found, with the permutation protected from mutability (either by copying with [:] or making immutable with tuple()). That is return to the next level, where it is extended on to the list that level is returning. Then at the top you will return a full list of permutations that you can sort
Craig "Ichabod" O'Brien - xenomind.com
I wish you happiness.
Recommended Tutorials: BBCode, functions, classes, text adventures
Reply


Possibly Related Threads…
Thread Author Replies Views Last Post
  "Plotting and Computation of Logistic Function by Using Taylor Series with Recursive canatilaa 1 1,786 May-13-2020, 04:01 PM
Last Post: jefsummers
  Homework advice - Boolean function, whole-word values musicjoeyoung 4 3,187 May-07-2020, 06:10 PM
Last Post: musicjoeyoung
  Help with Recursive solution,list items gianniskampanakis 8 3,506 Feb-28-2020, 03:36 PM
Last Post: gianniskampanakis
  Sum of elements on the list recursive sev 3 2,517 Jun-20-2019, 02:14 PM
Last Post: sev
  How to collect all integers with minimum number of rounds? meknowsnothing 6 3,178 Jun-11-2019, 08:36 PM
Last Post: jefsummers
  dictionaries and list as values Pippi 6 3,423 Apr-13-2019, 09:05 AM
Last Post: perfringo
  Turtle Graphics Card Values in a List Muzz 0 2,326 Apr-11-2019, 12:55 PM
Last Post: Muzz
  Recursive Function - Compare 2 lists, return the elements that don't exist in both KellyBaptist 1 5,179 Dec-23-2018, 10:10 AM
Last Post: Gribouillis
  finding the minimum value out of a set of inputs kannan 1 5,259 Oct-30-2018, 01:52 PM
Last Post: ichabod801
  making a dictionary from a list, one key with multiple values in a list within a list rhai 4 3,546 Oct-24-2018, 06:40 PM
Last Post: LeSchakal

Forum Jump:

User Panel Messages

Announcements
Announcement #1 8/1/2020
Announcement #2 8/2/2020
Announcement #3 8/6/2020