1

I'm looking to create a list of permutations between one item and a list in Python. For example:

[nyc]

[strawberry, apple, banana, orange, pineapple, ..]

I'm trying to get up to four words with 'nyc' always included. The order is important and 'nyc' must always be included. For example:

nyc
strawberry-nyc
nyc-strawberry 
strawberry-apple-nyc
strawberry-apple-banana-nyc

What I've done so far is put all the words into one list, include a few blanks, then create all permutations using itertools, then remove all the lines that don't conatain "nyc" :

import itertools
import re

# include blanks to allow for four-word permutations to have just one, two, or three words
adjectives =  ['', '', '', 'nyc', 'strawberry', 'apple', 'banana', 'orange', 'pineapple']
names = ['-'.join(x) for x in itertools.permutations(adjectives, 4)]

# limit to permutations that contain 'nyc'
names = [x for x in names if 'nyc' in x]

# since joining blanks using "-", remove the multiple dashes when this happens
# and also remove leading or trailing dashes
names = [re.sub(r"-+", "-", x) for x in names]
names = [re.sub(r"-+$", "", x) for x in names]
names = [re.sub(r"^-+", "", x) for x in names]

# remove duplicates, since blank can be added multiple times, sort for visual clarity
names = sorted(list(set(names)))

print(names)

I've been looking through itertools and some of the questions here, think I must be overlooking a simple solution. What would be a more effective way to do this?

Improve this question

4 Answers 4

Reset to default
2

This feels like a simple solution to me. Do the permutations and then add the 'nyc' into each position. I've avoided building too many of the intermediate results as full lists, so this should use less memory than solutions which involve building out lists and pruning them. I'm not sure about the performance.

import itertools

adjectives = ['strawberry', 'apple', 'banana', 'orange', 'pineapple']
root = 'nyc'

targetlength = 4

def rootpermute(root, adjectives, N):
    for group in itertools.permutations(adjectives, N-1):
        for position in range(len(group) + 1):
            newgroup = list(group)
            newgroup.insert(position, root)

            yield newgroup

perms = itertools.chain.from_iterable(rootpermute(root, adjectives, N) 
                                      for N in range(1, targetlength+1))

names = ['-'.join(group) for group in perms]
Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Looks like it gets the correct output! I'll have to parse through a little more, as a newbie. Going to do some testing.
1

How about permuting twice? Not very efficient for longer lists. For longer lists you can just insert nyc in all positions instead of permuting. I will leave the inner loop optimization for you.

import itertools
import re


adjectives = ['strawberry', 'apple', 'banana', 'orange', 'pineapple']
root = 'nyc'

for i in range(len(adjectives)):
    adj_perm = itertools.permutations(adjectives, i+1)
    for perm in adj_perm:
        perm = list(perm)
        perm.append(root)
        print(len(perm))
        combined_perm = itertools.permutations(perm, len(perm))
        for final_perm in combined_perm:
            print("-".join(final_perm))
Improve this answer

3 Comments

The output for this code is far longer, it looks like it's doing all permutations not only up to 4 words?
Oh yes, you are right. Restrict the first range to 3 instead of len(adjectives). With nyc it should be 4
Needed to add a line to remove the duplicates and add 'nyc' by itself (also removed the mid-function print statement).. works!
1

You can find all combinations of the items in the main list, and then apply a Cartesian Product:

def cart_p(d, c =[]):
   if not d:
     yield c
   else:
     for i in d[0]:
       yield from cart_p(d[1:], c+[i])

def combo(d, c = []):
  if len(c) == 3:
    yield c
  else:
    yield c
    for i in d:
       if i not in c:
          yield from combo(d, c+[i])

def group_result(r):
   for a, b in r:
     for i in range(1, len(a)):
        yield '-'.join(a[:i]+[b]+a[i:])
     yield from {'-'.join(a+[b]), '-'.join([b]+a)}

data = ['strawberry', 'apple', 'banana', 'orange', 'pineapple']
print(list(group_result(list(cart_p([list(combo(data)), ['nyc']])))))

Output:

['nyc', 'nyc-strawberry', 'strawberry-nyc', 'strawberry-nyc-apple', 'nyc-strawberry-apple', 'strawberry-apple-nyc', 'strawberry-nyc-apple-banana', 'strawberry-apple-nyc-banana', 'strawberry-apple-banana-nyc', 'nyc-strawberry-apple-banana', 'strawberry-nyc-apple-orange', 'strawberry-apple-nyc-orange', 'strawberry-apple-orange-nyc', 'nyc-strawberry-apple-orange', 'strawberry-nyc-apple-pineapple', 'strawberry-apple-nyc-pineapple', 'strawberry-apple-pineapple-nyc', 'nyc-strawberry-apple-pineapple', 'strawberry-nyc-banana', 'nyc-strawberry-banana', 'strawberry-banana-nyc', 'strawberry-nyc-banana-apple', 'strawberry-banana-nyc-apple', 'strawberry-banana-apple-nyc', 'nyc-strawberry-banana-apple', 'strawberry-nyc-banana-orange', 'strawberry-banana-nyc-orange', 'nyc-strawberry-banana-orange', 'strawberry-banana-orange-nyc', 'strawberry-nyc-banana-pineapple', 'strawberry-banana-nyc-pineapple', 'nyc-strawberry-banana-pineapple', 'strawberry-banana-pineapple-nyc', 'strawberry-nyc-orange', 'strawberry-orange-nyc', 'nyc-strawberry-orange', 'strawberry-nyc-orange-apple', 'strawberry-orange-nyc-apple', 'nyc-strawberry-orange-apple', 'strawberry-orange-apple-nyc', 'strawberry-nyc-orange-banana', 'strawberry-orange-nyc-banana', 'nyc-strawberry-orange-banana', 'strawberry-orange-banana-nyc', 'strawberry-nyc-orange-pineapple', 'strawberry-orange-nyc-pineapple', 'nyc-strawberry-orange-pineapple', 'strawberry-orange-pineapple-nyc', 'strawberry-nyc-pineapple', 'strawberry-pineapple-nyc', 'nyc-strawberry-pineapple', 'strawberry-nyc-pineapple-apple', 'strawberry-pineapple-nyc-apple', 'nyc-strawberry-pineapple-apple', 'strawberry-pineapple-apple-nyc', 'strawberry-nyc-pineapple-banana', 'strawberry-pineapple-nyc-banana', 'nyc-strawberry-pineapple-banana', 'strawberry-pineapple-banana-nyc', 'strawberry-nyc-pineapple-orange', 'strawberry-pineapple-nyc-orange', 'strawberry-pineapple-orange-nyc', 'nyc-strawberry-pineapple-orange', 'apple-nyc', 'nyc-apple', 'apple-nyc-strawberry', 'apple-strawberry-nyc', 'nyc-apple-strawberry', 'apple-nyc-strawberry-banana', 'apple-strawberry-nyc-banana', 'apple-strawberry-banana-nyc', 'nyc-apple-strawberry-banana', 'apple-nyc-strawberry-orange', 'apple-strawberry-nyc-orange', 'nyc-apple-strawberry-orange', 'apple-strawberry-orange-nyc', 'apple-nyc-strawberry-pineapple', 'apple-strawberry-nyc-pineapple', 'apple-strawberry-pineapple-nyc', 'nyc-apple-strawberry-pineapple', 'apple-nyc-banana', 'apple-banana-nyc', 'nyc-apple-banana', 'apple-nyc-banana-strawberry', 'apple-banana-nyc-strawberry', 'nyc-apple-banana-strawberry', 'apple-banana-strawberry-nyc', 'apple-nyc-banana-orange', 'apple-banana-nyc-orange', 'apple-banana-orange-nyc', 'nyc-apple-banana-orange', 'apple-nyc-banana-pineapple', 'apple-banana-nyc-pineapple', 'nyc-apple-banana-pineapple', 'apple-banana-pineapple-nyc', 'apple-nyc-orange', 'nyc-apple-orange', 'apple-orange-nyc', 'apple-nyc-orange-strawberry', 'apple-orange-nyc-strawberry', 'nyc-apple-orange-strawberry', 'apple-orange-strawberry-nyc', 'apple-nyc-orange-banana', 'apple-orange-nyc-banana', 'apple-orange-banana-nyc', 'nyc-apple-orange-banana', 'apple-nyc-orange-pineapple', 'apple-orange-nyc-pineapple', 'apple-orange-pineapple-nyc', 'nyc-apple-orange-pineapple', 'apple-nyc-pineapple', 'nyc-apple-pineapple', 'apple-pineapple-nyc', 'apple-nyc-pineapple-strawberry', 'apple-pineapple-nyc-strawberry', 'apple-pineapple-strawberry-nyc', 'nyc-apple-pineapple-strawberry', 'apple-nyc-pineapple-banana', 'apple-pineapple-nyc-banana', 'apple-pineapple-banana-nyc', 'nyc-apple-pineapple-banana', 'apple-nyc-pineapple-orange', 'apple-pineapple-nyc-orange', 'apple-pineapple-orange-nyc', 'nyc-apple-pineapple-orange', 'nyc-banana', 'banana-nyc', 'banana-nyc-strawberry', 'nyc-banana-strawberry', 'banana-strawberry-nyc', 'banana-nyc-strawberry-apple', 'banana-strawberry-nyc-apple', 'banana-strawberry-apple-nyc', 'nyc-banana-strawberry-apple', 'banana-nyc-strawberry-orange', 'banana-strawberry-nyc-orange', 'banana-strawberry-orange-nyc', 'nyc-banana-strawberry-orange', 'banana-nyc-strawberry-pineapple', 'banana-strawberry-nyc-pineapple', 'nyc-banana-strawberry-pineapple', 'banana-strawberry-pineapple-nyc', 'banana-nyc-apple', 'banana-apple-nyc', 'nyc-banana-apple', 'banana-nyc-apple-strawberry', 'banana-apple-nyc-strawberry', 'banana-apple-strawberry-nyc', 'nyc-banana-apple-strawberry', 'banana-nyc-apple-orange', 'banana-apple-nyc-orange', 'nyc-banana-apple-orange', 'banana-apple-orange-nyc', 'banana-nyc-apple-pineapple', 'banana-apple-nyc-pineapple', 'nyc-banana-apple-pineapple', 'banana-apple-pineapple-nyc', 'banana-nyc-orange', 'banana-orange-nyc', 'nyc-banana-orange', 'banana-nyc-orange-strawberry', 'banana-orange-nyc-strawberry', 'banana-orange-strawberry-nyc', 'nyc-banana-orange-strawberry', 'banana-nyc-orange-apple', 'banana-orange-nyc-apple', 'nyc-banana-orange-apple', 'banana-orange-apple-nyc', 'banana-nyc-orange-pineapple', 'banana-orange-nyc-pineapple', 'banana-orange-pineapple-nyc', 'nyc-banana-orange-pineapple', 'banana-nyc-pineapple', 'nyc-banana-pineapple', 'banana-pineapple-nyc', 'banana-nyc-pineapple-strawberry', 'banana-pineapple-nyc-strawberry', 'banana-pineapple-strawberry-nyc', 'nyc-banana-pineapple-strawberry', 'banana-nyc-pineapple-apple', 'banana-pineapple-nyc-apple', 'banana-pineapple-apple-nyc', 'nyc-banana-pineapple-apple', 'banana-nyc-pineapple-orange', 'banana-pineapple-nyc-orange', 'nyc-banana-pineapple-orange', 'banana-pineapple-orange-nyc', 'orange-nyc', 'nyc-orange', 'orange-nyc-strawberry', 'nyc-orange-strawberry', 'orange-strawberry-nyc', 'orange-nyc-strawberry-apple', 'orange-strawberry-nyc-apple', 'nyc-orange-strawberry-apple', 'orange-strawberry-apple-nyc', 'orange-nyc-strawberry-banana', 'orange-strawberry-nyc-banana', 'nyc-orange-strawberry-banana', 'orange-strawberry-banana-nyc', 'orange-nyc-strawberry-pineapple', 'orange-strawberry-nyc-pineapple', 'nyc-orange-strawberry-pineapple', 'orange-strawberry-pineapple-nyc', 'orange-nyc-apple', 'nyc-orange-apple', 'orange-apple-nyc', 'orange-nyc-apple-strawberry', 'orange-apple-nyc-strawberry', 'orange-apple-strawberry-nyc', 'nyc-orange-apple-strawberry', 'orange-nyc-apple-banana', 'orange-apple-nyc-banana', 'nyc-orange-apple-banana', 'orange-apple-banana-nyc', 'orange-nyc-apple-pineapple', 'orange-apple-nyc-pineapple', 'nyc-orange-apple-pineapple', 'orange-apple-pineapple-nyc', 'orange-nyc-banana', 'nyc-orange-banana', 'orange-banana-nyc', 'orange-nyc-banana-strawberry', 'orange-banana-nyc-strawberry', 'orange-banana-strawberry-nyc', 'nyc-orange-banana-strawberry', 'orange-nyc-banana-apple', 'orange-banana-nyc-apple', 'nyc-orange-banana-apple', 'orange-banana-apple-nyc', 'orange-nyc-banana-pineapple', 'orange-banana-nyc-pineapple', 'orange-banana-pineapple-nyc', 'nyc-orange-banana-pineapple', 'orange-nyc-pineapple', 'nyc-orange-pineapple', 'orange-pineapple-nyc', 'orange-nyc-pineapple-strawberry', 'orange-pineapple-nyc-strawberry', 'nyc-orange-pineapple-strawberry', 'orange-pineapple-strawberry-nyc', 'orange-nyc-pineapple-apple', 'orange-pineapple-nyc-apple', 'nyc-orange-pineapple-apple', 'orange-pineapple-apple-nyc', 'orange-nyc-pineapple-banana', 'orange-pineapple-nyc-banana', 'orange-pineapple-banana-nyc', 'nyc-orange-pineapple-banana', 'nyc-pineapple', 'pineapple-nyc', 'pineapple-nyc-strawberry', 'nyc-pineapple-strawberry', 'pineapple-strawberry-nyc', 'pineapple-nyc-strawberry-apple', 'pineapple-strawberry-nyc-apple', 'nyc-pineapple-strawberry-apple', 'pineapple-strawberry-apple-nyc', 'pineapple-nyc-strawberry-banana', 'pineapple-strawberry-nyc-banana', 'nyc-pineapple-strawberry-banana', 'pineapple-strawberry-banana-nyc', 'pineapple-nyc-strawberry-orange', 'pineapple-strawberry-nyc-orange', 'nyc-pineapple-strawberry-orange', 'pineapple-strawberry-orange-nyc', 'pineapple-nyc-apple', 'pineapple-apple-nyc', 'nyc-pineapple-apple', 'pineapple-nyc-apple-strawberry', 'pineapple-apple-nyc-strawberry', 'pineapple-apple-strawberry-nyc', 'nyc-pineapple-apple-strawberry', 'pineapple-nyc-apple-banana', 'pineapple-apple-nyc-banana', 'nyc-pineapple-apple-banana', 'pineapple-apple-banana-nyc', 'pineapple-nyc-apple-orange', 'pineapple-apple-nyc-orange', 'pineapple-apple-orange-nyc', 'nyc-pineapple-apple-orange', 'pineapple-nyc-banana', 'nyc-pineapple-banana', 'pineapple-banana-nyc', 'pineapple-nyc-banana-strawberry', 'pineapple-banana-nyc-strawberry', 'nyc-pineapple-banana-strawberry', 'pineapple-banana-strawberry-nyc', 'pineapple-nyc-banana-apple', 'pineapple-banana-nyc-apple', 'pineapple-banana-apple-nyc', 'nyc-pineapple-banana-apple', 'pineapple-nyc-banana-orange', 'pineapple-banana-nyc-orange', 'nyc-pineapple-banana-orange', 'pineapple-banana-orange-nyc', 'pineapple-nyc-orange', 'pineapple-orange-nyc', 'nyc-pineapple-orange', 'pineapple-nyc-orange-strawberry', 'pineapple-orange-nyc-strawberry', 'nyc-pineapple-orange-strawberry', 'pineapple-orange-strawberry-nyc', 'pineapple-nyc-orange-apple', 'pineapple-orange-nyc-apple', 'nyc-pineapple-orange-apple', 'pineapple-orange-apple-nyc', 'pineapple-nyc-orange-banana', 'pineapple-orange-nyc-banana', 'nyc-pineapple-orange-banana', 'pineapple-orange-banana-nyc']
>>>len(output)
311
Improve this answer

7 Comments

The output above looks like it only adds 'nyc' to the end of each line, not to any point within each line? Apologies if this was not clear in my post.
@octothorpe_not_hashtag No problem. So something like 'strawberry-nyc-apple', 'strawberry-nyc-apple-banana' are also necessary?
Correct, those are also necessary
@octothorpe_not_hashtag Will there always be only one value to add, i.e nyc, or could there be a listing of necessary additions such as ['nyc', 'ma', 'ca']?
Just one, eventually it might be a user defined input
|
0

IIUC you can use the following function with permuations and a list comprehension to get all length N combinations by inserting the root at each index. 

from itertools import permutations, chain

def getPerms(N, root, adjectives):
    """N is the number of elements from adjectives to include in the output"""
    if N == 0:
        return [root]
    return [
        "-".join(p[:i] + (root, ) + p[i:]) 
        for p in permutations(adjectives, N) 
        for i in range(N)
    ]

Now you can call this function to get the desired length combinations:

print(getPerms(0, root, adjectives))
#['nyc']

print(getPerms(1, root, adjectives))
#['nyc-strawberry', 'nyc-apple', 'nyc-banana', 'nyc-orange', 'nyc-pineapple']

So to get your final desired output, you can chain together calls to getPerms up to length 4:

res = list(chain.from_iterable(getPerms(i, root, adjectives) for i in range(4)))
print(res)
#['nyc',
# 'nyc-strawberry',
# 'nyc-apple',
# 'nyc-banana',
# 'nyc-orange',
# 'nyc-pineapple',
# 'nyc-strawberry-apple',
# 'strawberry-nyc-apple',
# 'nyc-strawberry-banana',
# 'strawberry-nyc-banana',
#... skipping ...
#'pineapple-nyc-orange-apple',
# 'pineapple-orange-nyc-apple',
# 'nyc-pineapple-orange-banana',
# 'pineapple-nyc-orange-banana',
# 'pineapple-orange-nyc-banana']

This produces an output list of 226 elements:

print(len(res))
#226
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.