CODEWITHSUNDEEP
pythonstring
Nima
Nima

Reputation: 40

all possible permutations for a string

Having a string='january' ,

how can I generate following cases:

case1(Replacing 1 character) => taking j and replace it with all ASCII letters(a-z). then do the same with: a , n , u , a , r , y.

Basically we would have

(Aanuary , Banuary ,..... ,Zanuary )+ (jAnuary , jBanuary .....jZanuary) + ....+(januarA , januarB , ....., januarZ)

I have done this part using following code, However, I have no idea how to do it for more than one letter since there are lots of permutations.

monthName= 'january'
asci_letters = ['a' , 'b' , .... , 'z']

lst = list(monthName)
indxs = [i for i , _ in enumerate(monthName)]
oneLetter=[]

for i in indxs:
word = monthName
pos = list(word)
    for j in asci_letters:
        pos[i] = j
        changed = ("".join(pos))
        oneLetter.append(changed)

Case2: Taking 2 characters and replacing them: (AAnuary , ABnuary ,.....,AZanuary) + (BAnuary , BBanuary, .... , BZanuary) + (AaAuary , AaBuary,.....,AaZuary) + ...... + (januaAB , .... , januaAZ)

Case3 : doing the same for 3 characters

Case7: doing the same for 7 characters(length of string)

To summarize, I want to create all possible cases of replacing, 1 letter, 2 letters,3 letters, up to all letters of a string.

Upvotes: 1

Views: 636

Answers (4)

Igl3
Igl3

Reputation: 5108

You can use itertools.combinations_with_replacement for this, which gives you an iterator with all permutations:

from itertools import combinations_with_replacement

# First Param is an iterable of possible values, second the length of the 
# resulting permutations
combinations = combinations_with_replacement('ABCDEFGHIJKLMNOPQRSTUVWXYZ',7)

# Then you can iterate like this:
for combination in combinations:
    #Do Stuff here

Don't try to convert this iterator to a list of all values, because you probably gonna get a MemoryException.

For your distance you might want to use python distance package. (You need to install it via pip first).

For your case, that you want to get all combinations for Characters a-z with length = 7 (because of January):

import distance
from itertools import combinations_with_replacement

str_to_compary_with = "JANUARY"

for i in range(len(str_to_compare_with):
    combinations = combinations_with_replacement('ABCDEFGHIJKLMNOPQRSTUVWXYZ', i+1)

    # Then you can iterate like this:
    for combination in combinations:
        # This is calculating the hamming distance for the combination with the string you want to compare to
        # Here you have to figure out yourself if you want to save that output to a file or whatever you wanna do with the distance
        hamming_dist = distance.hamming(''.join(combination), str_to_compare_with)

Upvotes: 1

ksha
ksha

Reputation: 2087

If you want to know how it is working, you can test this with a subset of letters, say from A-F:

x = []
for i in range(65,70): #subset of letters
    x.append(chr(i))

def recurse(string,index,arr):
    if(index>len(string)-1):
        return
    for i in range(index,len(string)):
        for item in x:
            temp = string[:i]+item+string[i+1:]
            arr.append(temp)
            recurse(temp,i+1,arr)

arr = []
recurse('abc',0,arr)
print arr

Upvotes: 0

MSeifert
MSeifert

Reputation: 152850

It's very likely that you can't hold all these permutations in memory because it will quickly become very crowded.

But to get all indices for the cases you can use itertools.combinations. For 1 it will give the single indices:

from itertools import combinations

string_ = 'january'
length = len(string_)
print(list(combinations(range(length), 1)))
# [(0,), (1,), (2,), (3,), (4,), (5,), (6,)]

Likewise you can get the indices for case 2-7:

print(list(combinations(range(length), 2)))
# [(0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (1, 2), (1, 3), (1, 4), 
#  (1, 5), (1, 6), (2, 3), (2, 4), (2, 5), (2, 6), (3, 4), (3, 5), (3, 6), 
#  (4, 5), (4, 6), (5, 6)]

Then it's just a matter of inserting the itertools.product of string.ascii_uppercase at the given indices:

from itertools import product
import string

print(list(product(string.ascii_uppercase, repeat=1)))
# [('A',), ('B',), ('C',), ('D',), ('E',), ('F',), ('G',), ('H',), ('I',),
#  ('J',), ('K',), ('L',), ('M',), ('N',), ('O',), ('P',), ('Q',), ('R',), 
#  ('S',), ('T',), ('U',), ('V',), ('W',), ('X',), ('Y',), ('Z',)]

Likewise for different repeats given the "case".

Putting this all together:

def all_combinations(a_string, case):
    lst = list(a_string)
    length = len(lst)
    for combination in combinations(range(length), case):
        for inserter in product(string.ascii_uppercase, repeat=case):
            return_string = lst.copy()
            for idx, newchar in zip(combination, inserter):
                return_string[idx] = newchar
            yield ''.join(return_string)

Then you can get all desired permutations for each case by:

list(all_combinations('january', 2))   # case2

list(all_combinations('january', 4))   # case4

list(all_combinations('january', 7))   # case7

Or if you need all of them:

res = []
for case in [1, 2, 3, 4, 5, 6, 7]:
    res.extend(all_combinations('january', case))

But that will require a lot of memory.

Upvotes: 1

zipa
zipa

Reputation: 27899

This should do everything that you wanted with help of product and permutations:

from itertools import product, permutations

monthName= 'january'

letters = list('abcdefghijklmnopqrstuvwxyz')

n = len(monthName)
indxs = range(n)
mn = list(monthName)

cases = {k: [] for k in range(2, n+1)}
for num in range(2, n+1):
    letter_combos = list(product(*[letters for _ in range(num)]))
    positions = permutations(indxs, num)
    for p in positions:
        for l in letter_combos:
            l = iter(l)
            for i in p:
                mn[i] = next(l)
            mn = ''.join(mn)
            cases[num].append(mn)
            mn = list(monthName)

Upvotes: 0

Related Questions