0

I need to input a string,and returns its next lexicographically bigger string.For example, the next string of 'anmdfg' is 'anmdgf'.However,the length of the input could be very large,it may include 100 characters or more,and there will be some repeated characters in it.So I decide to use itertools.permutations without making it into a list for avoiding the memory over-consumption.

#!/usr/bin/env python3
from itertools import permutations

a = list(input())
tuple_a = tuple(a)
b = permutations(a,len(a))
p = next(b)
result = ''

try:
    while 1:
        p = next(b)        
        if p > tuple_a:
            result = ''.join(p)
            print(result)
        break

except:
    if result == '':
        print('No answer.')
else:
    if result == '':
        print('No answer.')

The b in my sample isn't sorted.It seems that I have to generate the list first.I tried and it consumed my memory so fast that I had no time to terminate the process. Is there any way for me to sort the result of permutation without making a list?

Haohu Shen
  • 58
  • 1
  • 7
  • Rather than `while 1: p = b.__next__()` do `for p in b:`. Directly calling internal "dunder" methods like `__next__` is strongly discouraged. – jonrsharpe Nov 09 '16 at 11:46
  • b is not a list,it is only a generator. – Haohu Shen Nov 09 '16 at 11:50
  • Erm, yes, and you can still iterate over a generator. That's basically the point of them. Even if that weren't true, you should be using the public interface `next(thing)` not the private interface `thing.__next__()`. – jonrsharpe Nov 09 '16 at 11:53

5 Answers5

2

It's really, really inefficient to generate all permutations less than the output. Better to use the classic linear-time algorithm implemented below:

def nextperm(lst):
  for i in range(len(lst) - 1, 0, -1):
    if lst[i-1] < lst[i]:
      for j in range(len(lst) - 1, i-1, -1):
        if lst[i-1] < lst[j]:
          return lst[:i-1] + lst[j:j+1] + lst[:j:-1] + lst[i-1:i] + lst[j-1:i-1:-1]
David Eisenstat
  • 64,237
  • 7
  • 60
  • 120
  • Yes,it's more efficient.I think the most important issue is that I use the sort built-in function in Python3 and it's complexity is O(nlgn).So it was wrong to sort the input in the first place. – Haohu Shen Nov 10 '16 at 12:13
  • In another word,the method of making a permutation and sorting is inefficient thought there is no need to make a permutated list. – Haohu Shen Nov 10 '16 at 12:21
0

I think the itertools-y way to do this is:

from itertools import dropwhile, permutations

def next_largest(start):
    """Return the next largest permutation of the characters in start."""
    reference = tuple(start)
    try:
        return next(dropwhile(
            lambda p: p <= reference, 
            permutations(sorted(start))
        ))
    except StopIteration:
        raise ValueError('No larger string available')

Note that you sort start before generating permutations, to ensure that the permutations are being generated in lexicographical order.

Also note that:

  1. I have been specific about the error I want to catch, allowing any unexpected errors that occur to propagate correctly (see "The evils of except:"); and
  2. I'm using next(thing) rather than thing.__next__() (see What is the relationship between the Python data model and built-in functions?).
Community
  • 1
  • 1
jonrsharpe
  • 115,751
  • 26
  • 228
  • 437
  • Thx for answering and the tips.It is correct.I was not familiar with dropwhile so I didn't consider it for the first place. – Haohu Shen Nov 09 '16 at 12:29
0

try this,

def NextHighestWord(string):
    S = [ord(i) for i in string]
    #find non-incresing suffix from last
    i = len(S) - 1
    while i > 0 and S[i-1] >= S[i]:
        i = i - 1
    if i <= 0:
        return False

    #next element to highest is pivot
    j = len(S) - 1
    while S[j] <= S[i -1]:
        j = j - 1
    S[i-1],S[j] = S[j],S[i-1]

    #reverse the suffix
    S[i:] = S[len(S) - 1 : i-1 : -1]
    ans = [chr(i) for i in S]
    ans = "".join(ans)
    print(ans)
    return True

test = int(input())
for i in range(test):
    s = input()
    val = NextHighestWord(s)
    if val:
        continue
    else:
        print("no answer")
Rehan Shikkalgar
  • 1,029
  • 8
  • 16
0

The generic way will be to:

  1. Find all the permutations of the string as list.
  2. Sort the list
  3. Find the index of your item
  4. Then get the item next to it

Below is the code to achieve that:

>>> from itertools import permutations

>>> my_string = 'anmdfg'

# Permutation of all the strings
>>> all_strings = list(permutations(my_string, len(my_string)))

# Sorted lexicographically
>>> all_string = sorted(all_strings)

# index of current string
>>> my_index = all_string.index(tuple(my_string))

# Next item (but as tuple)
>>> next_value = all_string[my_index+1]
>>> next_value
('a', 'n', 'm', 'd', 'g', 'f')

# Convert tuple to string
>>> ''.join(next_value)
'anmdgf'
Moinuddin Quadri
  • 46,825
  • 13
  • 96
  • 126
0

Relatively simpler implementation using python for generating next permutation.

    def nextperm(s):
        l=[]
       for i in range(len(s)):
        l.append(s[i])
       for i in range(-1,-len(s),-1):
         if (l[i] > l[i-1]):
           break
         else:
          pass
       pos=len(s)+(i-1)
      for i in range(pos,len(s),1):
           if (l[pos] > l[i]):
            (l[pos],l[i-1])=(l[i-1],l[pos])
              break
           else:
             pass
      l=l[:pos+1]+l[-1:-(len(s)-pos):-1]  
      s1=''.join(l)
      return(s1)
mohit tyagi
  • 1
  • 1