Étant donné un nombre, trouver le prochain plus grand nombre qui a exactement les mêmes chiffres que le nombre d'origine

Question

J'ai juste bombardé une interview et fait à peu près nulle progrès sur ma question d'entrevue. Quelqu'un peut-il me dire comment faire cela? J'ai essayé de chercher en ligne, mais ne pouvais pas trouver quoi que ce soit:

Étant donné un nombre, trouver le prochain plus grand nombre qui a exactement le même ensemble de chiffres que le nombre d'origine. Par exemple: étant donné 38276 retour 38627

Je voulais commencer par trouver l'index du premier chiffre (à partir de la droite) qui était de moins que le chiffre des unités. Alors je voudrais faire tourner les derniers chiffres dans le sous-ensemble tel qu'il a été le prochain plus grand nombre composé des mêmes chiffres, mais s'est coincé.

L'enquêteur a également suggéré d'essayer de permuter les chiffres un à un moment, mais je ne pouvais pas comprendre l'algorithme et le regarda d'un écran pendant 20 à 30 minutes. Inutile de dire, je pense que je vais continuer la chasse au travail.

edit: pour ce que sa vaut le coup, j'ai été invité à la prochaine ronde d'entrevues

Answer 1

Vous pouvez le faire dans O(n) (où n est le nombre de chiffres) comme ceci:

En partant de la droite, vous trouvez la première paire de chiffres tels que le chiffre de gauche est plus petite que la droite chiffres. Nous allons voir à la gauche des chiffres par les "chiffres-x". Trouver le plus petit nombre de plus que chiffres-x à droite de chiffres-x, et le placer immédiatement à la gauche du chiffre-x. Enfin, trier le reste des chiffres dans l'ordre croissant, depuis qu'ils étaient déjà en descendant de l'ordre, tout ce que vous devez faire est de revenir en arrière (à l'exception des chiffres-x, qui peut être placé au bon endroit en O(n)).

Un exemple permettra de rendre cela plus clair:

123456784987654321
démarrer avec un certain nombre

123456784 987654321
 ^le premier endroit où les le chiffre de gauche est moins que le chiffre de droite est ici. 
 Le caractère "x" est 4

123456784 987654321
 ^trouver le plus petit chiffre de plus de 4 vers la droite

123456785 4 98764321
 ^le placer à la gauche de 4

123456785 4 12346789
123456785123446789
 ^trier les chiffres à droite de 5. Depuis les toutes sauf 
 le '4' étaient déjà dans l'ordre décroissant, tout ce que nous devons faire est de 
 inverser leur ordre, et de trouver la bonne place pour le '4'

Answer 2

Voir ici:

http://code.google.com/codejam/contest/dashboard?c=186264#s=a&a=1

Exemple:

34722641

A. Diviser la séquence de chiffres à deux, de sorte que la partie droite est aussi longue que possible, tout en restant dans l'ordre décroissant:

34722 641

B. Prenez le dernier chiffre de la première séquence, et de l'échanger avec le plus petit chiffre dans la seconde qui est plus grand qu'elle:

3472(2) 6(4)1
->
34724 621

C. Trier la deuxième séquence dans l'ordre croissant:

34724 126

D. Fait!

34724126

Answer 3

Voici un compact (mais en partie la force brute) solution en Python

def findnext(ii): return min(v for v in (int("".join(x)) for x in
    itertools.permutations(str(ii))) if v>ii)

En C++, vous pouvez faire le permutations comme ceci: http://stackoverflow.com/a/9243091/1149664 (C'est le même algorithme que celui de itertools)

Voici une mise en œuvre de la réponse sommet décrite par Weeble et BlueRaja, (autres réponses). Je doute qu'il ya quelque chose de mieux.

def findnext(ii):
    iis=map(int,str(ii))
    for i in reversed(range(len(iis))):
        if i == 0: return ii
        if iis[i] > iis[i-1] :
            break        
    left,right=iis[:i],iis[i:]
    for k in reversed(range(len(right))):
        if right[k]>left[-1]:
           right[k],left[-1]=left[-1],right[k]
           break
    return int("".join(map(str,(left+sorted(right)))))

Answer 4

Au moins, ici sont un couple de l'exemple de la force brute de Chaîne en fonction des solutions, que vous auriez été en mesure de venir avec le bouton droit sur le dessus de votre tête:

la liste de chiffres en 38276 triés est - 23678

la liste de chiffres en 38627 triés est - 23678

la force brute de l'incrément, de tri et de comparaison

Le long de la force brute des solutions serait de convertir une Chaîne de caractères et de la force brute de tous les nombres possibles à l'aide de ces chiffres.

Créer des services de renseignements de tous, les mettre dans une liste et de les trier,les la prochaine entrée après l'entrée cible.

Si vous avez passé 30 minutes sur ce sujet et de ne pas au moins au moins une approche par force brute, je ne voudrais pas vous embaucher.

Dans le monde de l'entreprise, une solution peu élégante, lent et maladroit, mais fait le travail est toujours plus de valeur que pas de solution du tout, en fait, assez bien décrit tous les logiciels d'affaires, inélégant, lent et maladroit.

Answer 5

Votre idée

Je voulais commencer par trouver l'index du premier chiffre (à partir de la droite) qui était de moins que le chiffre des unités. Alors je voudrais faire tourner les derniers chiffres dans le sous-ensemble tel qu'il a été le prochain plus grand nombre composé des mêmes chiffres, mais s'est coincé.

est assez bonne, en fait. Vous venez de prendre en compte non seulement le dernier chiffre, mais tous les chiffres de moins en moins d'importance que la actuellement à l'étude. Qui est atteint, nous avons une fonction monotone de la séquence de chiffres, c'est le chiffre droite plus petit que son voisin de droite. Sujet

1234675
    ^

Le prochain plus grand nombre d'avoir les mêmes chiffres est

1234756

Le trouvé chiffre est échangé pour le dernier chiffre est le plus petit des chiffres et les chiffres restants sont disposées en ordre croissant.