How can I write a function that use as many 'for loops' as requested for anagramming a list with empty spaces using a list with letter strings?

Question

Hello stackoverflow community! I've been trying to find a way to do this for some weeks without looking up for help(kinda personal challenge),but I couldn't, and with college projects taking most of my time,not being able to do this is frustating me, because it don't seem too hard, but can't think of how to do it. First lesson to become a dev is to learn to cooperate with others, right? So I'm here to ask for help. I have this code:

l = [None]*8
k = ['m','i','k','e']
for a in k: 
   for b in k: 
       for c in k: 
          l[0] = a 
          l[1] = b 
          l[2] = c 
          print(l)

That output this:

['m', 'm', 'm', None, None, None, None, None]
['m', 'm', 'i', None, None, None, None, None]
['m', 'm', 'k', None, None, None, None, None]
['m', 'm', 'e', None, None, None, None, None]
['m', 'i', 'm', None, None, None, None, None]
['m', 'i', 'i', None, None, None, None, None]
['m', 'i', 'k', None, None, None, None, None]
['m', 'i', 'e', None, None, None, None, None]
['m', 'k', 'm', None, None, None, None, None]
['m', 'k', 'i', None, None, None, None, None]
['m', 'k', 'k', None, None, None, None, None]
['m', 'k', 'e', None, None, None, None, None]
['m', 'e', 'm', None, None, None, None, None]
['m', 'e', 'i', None, None, None, None, None]
['m', 'e', 'k', None, None, None, None, None]
['m', 'e', 'e', None, None, None, None, None]
['i', 'm', 'm', None, None, None, None, None]
['i', 'm', 'i', None, None, None, None, None]
['i', 'm', 'k', None, None, None, None, None]
['i', 'm', 'e', None, None, None, None, None]
['i', 'i', 'm', None, None, None, None, None]
['i', 'i', 'i', None, None, None, None, None]
['i', 'i', 'k', None, None, None, None, None]
['i', 'i', 'e', None, None, None, None, None]
['i', 'k', 'm', None, None, None, None, None]
['i', 'k', 'i', None, None, None, None, None]
['i', 'k', 'k', None, None, None, None, None]
['i', 'k', 'e', None, None, None, None, None]
['i', 'e', 'm', None, None, None, None, None]
['i', 'e', 'i', None, None, None, None, None]
['i', 'e', 'k', None, None, None, None, None]
['i', 'e', 'e', None, None, None, None, None]
['k', 'm', 'm', None, None, None, None, None]
['k', 'm', 'i', None, None, None, None, None]
['k', 'm', 'k', None, None, None, None, None]
['k', 'm', 'e', None, None, None, None, None]
['k', 'i', 'm', None, None, None, None, None]
['k', 'i', 'i', None, None, None, None, None]
['k', 'i', 'k', None, None, None, None, None]
['k', 'k', 'm', None, None, None, None, None]
['k', 'k', 'i', None, None, None, None, None]
['k', 'k', 'k', None, None, None, None, None]
['k', 'k', 'e', None, None, None, None, None]
['k', 'e', 'm', None, None, None, None, None]
['k', 'e', 'i', None, None, None, None, None]
['k', 'e', 'k', None, None, None, None, None]
['k', 'e', 'e', None, None, None, None, None]
['e', 'm', 'm', None, None, None, None, None]
['e', 'm', 'i', None, None, None, None, None]
['e', 'm', 'k', None, None, None, None, None]
['e', 'm', 'e', None, None, None, None, None]
['e', 'i', 'm', None, None, None, None, None]
['e', 'i', 'i', None, None, None, None, None]
['e', 'i', 'k', None, None, None, None, None]
['e', 'i', 'e', None, None, None, None, None]
['e', 'k', 'm', None, None, None, None, None]
['e', 'k', 'i', None, None, None, None, None]
['e', 'k', 'k', None, None, None, None, None]
['e', 'k', 'e', None, None, None, None, None]
['e', 'e', 'm', None, None, None, None, None]
['e', 'e', 'i', None, None, None, None, None]
['e', 'e', 'k', None, None, None, None, None]
['e', 'e', 'e', None, None, None, None, None]

What I want to do, is have a funtion that do this to how many spaces in nonelist I want.Like passing an argument that choses how many None I want to substitute. I imagined how this funtion would work, and in my mind it had 3 arguments (size of the None list,list with letters to substitute,number of None to substitute). I'm familiar with recursion, but couldn't think of a way to implement this using it. Thanks in advance :)

It's a little hard to read the description, but I believe that you can solve your problem with the **itertools** package and a small amount of list manipulation, . — Prune, Jan 20 '17 at 18:58
To approach a problem like this, start with the smallest part of it and put it in a function. In this case it would be the innermost loop. Then you can compose the other parts based on calling the function you have defined. — dsh, Jan 20 '17 at 19:09

Yevhen Kuzmovych · Answer 1 · 2017-01-20T22:58:42.273

3

Recursion is the way to go:

def print_permutations(k, l, level = 0):
    if level == len(l):
        print(l)
    else:
        for a in k:
            l[level] = a
            print_permutations(k, l, level+1 )



l = [None]*8
k = ['m','i','k','e']

print_permutations(k, l)

Or you can use standart tools:

from itertools import combinations_with_replacement


k = ['m','i','k','e']

for p in combinations_with_replacement(k, 8):
    print(p) 
    # print(list(p)) if you want to print it as a list

And btw. k='mike' would work the same.

edited Jan 20 '17 at 22:58

answered Jan 20 '17 at 18:55

Yevhen Kuzmovych

10,940
7
28
48

Dont you want `itertools.permutations`? – juanpa.arrivillaga Jan 20 '17 at 19:09
1

@juanpa.arrivillaga I do want it, but it does not do what OP asks for :) Try it yourself. – Yevhen Kuzmovych Jan 20 '17 at 19:13
Ah, I think I was thrown off by "anagraming" – juanpa.arrivillaga Jan 20 '17 at 19:16
Gave me a great idea for what I want. Thank you! – Mikael Jan 20 '17 at 22:48

Khaled Hamed · Answer 2 · 2017-01-20T19:25:20.217

1

def func(n, list, k):
    if n == 0:
        print(list)
    else:
        for i in k:
            list.append(i)
            func(n - 1, list)
            list.pop()

You pass the number and an empty list and the list k

edited Jan 20 '17 at 19:25

answered Jan 20 '17 at 18:57

Khaled Hamed

85
1
3
10

1

You should pass `k` too. And `list` will override pythons `list` which is not a problem in this case, but genuinely a bad practice. – Yevhen Kuzmovych Jan 20 '17 at 19:04
@YevhenKuzmovych no need to keep passing `k` at at each call. It is more efficient to make it global. – Khaled Hamed Jan 20 '17 at 19:07
@KhaledHamed how is it "more efficient"? – juanpa.arrivillaga Jan 20 '17 at 19:07
@juanpa.arrivillaga when you pass a parameter to a function, you copy that element into the function, for example if the depth of the recursion went to 10,000 we would have 10,000 `k`s which are all the same. So having just one is "more efficient" because it takes less memory and less time (for copying). – Khaled Hamed Jan 20 '17 at 19:10
1

@KhaledHamed As far as I am aware, Python doesn't function that way, or I am not understanding what you are saying. Global lookups take a lot of overhead in Python, and generally make your code run slower than passing a parameter. – juanpa.arrivillaga Jan 20 '17 at 19:12
@juanpa.arrivillaga howcome that global lookup take more than copying a whole list into a new one. That may apply with small list, but not with a big one. – Khaled Hamed Jan 20 '17 at 19:15
@KhaledHamed Python does not copy the whole list when it passed to a function. It works with references. – Yevhen Kuzmovych Jan 20 '17 at 19:16
@KhaledHamed arguments does not get copied in python. – juanpa.arrivillaga Jan 20 '17 at 19:17
Try an experiment: `def mutate(lst): lst.append(1); x = []; mutate(x); print(x)` and you will see that `x` is not copied. – juanpa.arrivillaga Jan 20 '17 at 19:20
Yes, I was wrong. I thought it's like C++, seems that things are alot [different](http://stackoverflow.com/questions/986006/how-do-i-pass-a-variable-by-reference) in Python. Thanks :) – Khaled Hamed Jan 20 '17 at 19:23

score 1 · Answer 3 · answered Jan 20 '17 at 19:00

the solution is to use recursion.

I'll show you pseudocode:

suppose you want to fill until index 6 of nonelist (or l)

fillNoneList(nonelist, word, index, size):
    if index <= size:
        for c in word:
            nonelist[index] = c
            fillNoneList(nonelist, word, index + 1, size)
        end-for
    else:
        HERE YOU PRINT, BECAUSE YOU REACHED THE END
end

then you just call fillNoneList(l, k, 0, 6) and you are done :)

Shiping · Answer 4 · 2017-01-21T03:17:38.323

You can just manipulate/cycle an index list to get the permutation.

#!/usr/bin/env python

"""
example: mklist mike 8 3
['m', 'm', 'm', None, None, None, None, None]
['m', 'm', 'i', None, None, None, None, None]
['m', 'm', 'k', None, None, None, None, None]
['m', 'm', 'e', None, None, None, None, None]
['m', 'i', 'm', None, None, None, None, None]
...
"""

import sys
import re

prog = re.sub(".*\/","",sys.argv[0])

if len(sys.argv) < 4:
    print("Usage: %s string nonesize replacesize" % (prog))
    quit()

def makeList(k, l, n):
    if n < 1: return
    if n > len(l): return

    idx = [0]*n
    s = len(k)
    r = []
    for i in reversed(range(n)):
        r.append(i)

    while n > -1:
        for i in r:
            l[i] = k[idx[i]]
        print(l)
        for i in r:
            idx[i] += 1
            if idx[i] < s:
                break
            else:
                n = i - 1
                idx[i] = 0


makeList(sys.argv[1], ['None'] * int(sys.argv[2]), int(sys.argv[3]))

How can I write a function that use as many 'for loops' as requested for anagramming a list with empty spaces using a list with letter strings?

4 Answers4