CODEWITHSUNDEEP
pythonsubstring
Amon
Amon

Reputation: 2951

Finding permutations of lists using sublists

I was looking at this website about recursion. Where I found this example of using recursion to find the permutations of a list of people:

def fill_seats(people):
   # Return a list of ways to fill len(people) seats with the people
   # named in the sequence people.
   if len(people) == 0:
       return []
   else:
      possible = []
      for i in range(len(people)):
         this_person = people[i]
         everyone_else = people[:i] + people[i+1:]
         for seating_arrangement in fill_seats(everyone_else):
            possible = possible + [[this_person] + seating_arrangement]
      return possible

our_class = ["Biella", "Gwen", "Katie", "Seth", "Will"]

for arrangement in fill_seats(our_class):
    print arrangement

print len(fill_seats(our_class)), "total possible arrangements."

However it keeps return 0 and I have no idea why, any ideas? And how exactly are the substrings working in this case? Don't they just splice the individual items in the list? What purpose would that have?

Upvotes: 0

Views: 143

Answers (2)

jayelm
jayelm

Reputation: 7657

To answer your question about the slicing, these aren't substrings, they're sublists. For example, if people is the following list:

people = ['Adam', 'Betsy', 'Charlie', 'David']

We begin iterating through every index in people. So our first iteration would assign

>>> this_person = people[0]
>>> this_person
'Adam'

And then everyone_else would be:

>>> people[:0]
[]
>>> people[1:]
['Betsy', 'Charlie', 'David']
>>> everyone_else = people[:0] + people[1:]
>>> everyone_else
['Betsy', 'Charlie', 'David']

Basically, you're reconstructing the list leaving out the current index i, then recursing with the smaller list.

When i = 1, it looks like this:

>>> this_person = people[1]
'Betsy'
>>> people[:1]
['Adam']
>>> people[2:]
['Charlie', 'David']
>>> everyone_else = people[:1] + people[2:]
>>> everyone_else
['Adam', 'Charlie', 'David']

Upvotes: 1

thefourtheye
thefourtheye

Reputation: 239443

All you need to change is

if len(people) == 1:
    return [people]

Because, when people is [], it returns an empty list. So, if people has only one element, the fill_seats(everyone_else) will return [], so possible will also return []. The same is returned through the chain and finally returned back.

With that change, the output becomes

['Biella', 'Gwen', 'Katie', 'Seth', 'Will']
['Biella', 'Gwen', 'Katie', 'Will', 'Seth']
['Biella', 'Gwen', 'Seth', 'Katie', 'Will']
...
...
...
['Will', 'Seth', 'Gwen', 'Katie', 'Biella']
['Will', 'Seth', 'Katie', 'Biella', 'Gwen']
['Will', 'Seth', 'Katie', 'Gwen', 'Biella']
120 total possible arrangements.

Upvotes: 2

Related Questions