468,769 Members | 2,180 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 468,769 developers. It's quick & easy.

Permutation String

2 2Bits
Hi everyone... Can someone help me?

Expand|Select|Wrap|Line Numbers
  1. def lexico_permute_string(s):
  2.     ''' Generate all permutations in lexicographic order of string `s`
  3.  
  4.         This algorithm, due to Narayana Pandita, is from
  5.         https://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order
  6.  
  7.         To produce the next permutation in lexicographic order of sequence `a`
  8.  
  9.         1. Find the largest index j such that a[j] < a[j + 1]. If no such index exists, 
  10.         the permutation is the last permutation.
  11.         2. Find the largest index k greater than j such that a[j] < a[k].
  12.         3. Swap the value of a[j] with that of a[k].
  13.         4. Reverse the sequence from a[j + 1] up to and including the final element a[n].
  14.     '''
  15.  
  16.     a = sorted(s)
  17.     n = len(a) - 1
  18.     while True:
  19.         yield ''.join(a)
  20.  
  21.         #1. Find the largest index j such that a[j] < a[j + 1]
  22.         for j in range(n-1, -1, -1):
  23.             if a[j] < a[j + 1]:
  24.                 break
  25.         else:
  26.             return
  27.  
  28.         #2. Find the largest index k greater than j such that a[j] < a[k]
  29.         v = a[j]
  30.         for k in range(n, j, -1):
  31.             if v < a[k]:
  32.                 break
  33.  
  34.         #3. Swap the value of a[j] with that of a[k].
  35.         a[j], a[k] = a[k], a[j]
  36.  
  37.         #4. Reverse the tail of the sequence
  38.         a[j+1:] = a[j+1:][::-1]
  39.  
  40. for s in lexico_permute_string('data):
OUTPUT :
aadt
aatd
adat
adta
atad
atda
daat
data
dtaa
taad
tada
tdaa

CAN OUTPUT TO :
data
data
daat
dtaa
dtaa
daat
data
adta
adat
atda
atad
aadt
aatd
tdaa
tdaa
tada
taad
tada
taad
adat
adta
aadt
aatd
atda
atad
Jun 15 '21 #1
3 2726
SioSio
252 128KB
I don't know what to help, but the syntax is wrong.
Expand|Select|Wrap|Line Numbers
  1. for s in lexico_permute_string('data’):
Jun 15 '21 #2
gieforce
2 2Bits
Expand|Select|Wrap|Line Numbers
  1. def lexico_permute_string(s):
  2.     ''' Generate all permutations in lexicographic order of string `s`
  3.  
  4.         This algorithm, due to Narayana Pandita, is from
  5.         https://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order
  6.  
  7.         To produce the next permutation in lexicographic order of sequence `a`
  8.  
  9.         1. Find the largest index j such that a[j] < a[j + 1]. If no such index exists, 
  10.         the permutation is the last permutation.
  11.         2. Find the largest index k greater than j such that a[j] < a[k].
  12.         3. Swap the value of a[j] with that of a[k].
  13.         4. Reverse the sequence from a[j + 1] up to and including the final element a[n].
  14.     '''
  15.  
  16.     a = sorted(s)
  17.     n = len(a) - 1
  18.     while True:
  19.         yield ''.join(a)
  20.  
  21.         #1. Find the largest index j such that a[j] < a[j + 1]
  22.         for j in range(n-1, -1, -1):
  23.             if a[j] < a[j + 1]:
  24.                 break
  25.         else:
  26.             return
  27.  
  28.         #2. Find the largest index k greater than j such that a[j] < a[k]
  29.         v = a[j]
  30.         for k in range(n, j, -1):
  31.             if v < a[k]:
  32.                 break
  33.  
  34.         #3. Swap the value of a[j] with that of a[k].
  35.         a[j], a[k] = a[k], a[j]
  36.  
  37.         #4. Reverse the tail of the sequence
  38.         a[j+1:] = a[j+1:][::-1]
  39.  
  40. for s in lexico_permute_string('data'):
Sorry...
Jun 15 '21 #3
SioSio
252 128KB
Does that mean including duplicate characters?
Expand|Select|Wrap|Line Numbers
  1. import itertools
  2. all = itertools.permutations('data', 4)
  3. for x in all:
  4.     print(''.join(x))
Jun 16 '21 #4

Post your reply

Sign in to post your reply or Sign up for a free account.

Similar topics

10 posts views Thread by Talin | last post: by
3 posts views Thread by Jack Middleton | last post: by
27 posts views Thread by onkar | last post: by
3 posts views Thread by Csaba Gabor | last post: by
20 posts views Thread by anurag | last post: by
reply views Thread by zhoujie | last post: by
1 post views Thread by Marin | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.