Next highest int from digits: Difference between revisions

integer using only the given digits^*1.

 

 

 

;Algorithm 1:

 

The above could prove slow and memory hungry for numbers with large numbers of

 

;Algorithm 2:

 

<pre>

n = 12453

 

This second algorithm is faster and more memory efficient, but implementations

 

 

;Task requirements:

Calculate the next highest int from the digits of the following numbers:

 

;Optional stretch goal:

 

=={{header|Factor}}==

This uses the <code>next-permutation</code> word from the <code>math.combinatorics</code> vocabulary. <code>next-permutation</code> wraps around and returns the smallest lexicographic permutation after the largest one, so additionally we must check if we're at the largest permutation and return zero if so. See the implementation of <code>next-permutation</code> [https://docs.factorcode.org/content/word-next-permutation%2Cmath.combinatorics.html here].

{{works with|Factor|0.99 2020-01-23}}

math.parser sequences ;

 

9589776899767587796600

}

{{out}}

<pre>

9589776899767587796600 -> 9589776899767587900667

</pre>

 

=={{header|Go}}==

This uses a modified version of the recursive code in the [[https://rosettacode.org/wiki/Permutations#Go Permutations#Go]] task.

 

import (

algorithm1(nums[:len(nums)-1]) // exclude the last one

algorithm2(nums) // include the last one

 

{{out}}

{{Trans|Python}}

(Generator version)

 

digitShuffleSuccessors :: Integer -> [Integer]

(fmap . (+) <*> (nub . sort . concatMap go . permutations . show)) n

where

 

main :: IO ()

main =

12

' '

show harvest)

digitShuffleSuccessors

[0, 9, 12, 21, 12453, 738440, 45072010, 95322020]

 

fTable :: String -> (a -> String) -> (b -> String) -> (a -> b) -> [a] -> String

fTable s xShow fxShow f xs =

unlines $

where

w = maximum (length . xShow <$> xs)

 

rjust :: Int -> Char -> String -> String

{{Out}}

<pre>Taking up to 5 digit-shuffle successors of a positive integer:

(The digit-swap approach makes it feasible to obtain successors of this kind for much larger numbers)

 

digitShuffleSuccessors n =

minimalSwap ([], xs) = []

minimalSwap (_, []) = []

main :: IO ()

main = do

putStrLn $

fTable

show

let harvest = take 5 xs

digitShuffleSuccessors

[0, 9, 12, 21, 12453, 738440, 45072010, 95322020]

putStrLn $

fTable

"Taking up to 10 digit-shuffle successors of a larger integer:\n"

show

(take 10 . digitShuffleSuccessors)

[9589776899767587796600]

reversedDigits 0 = [0]

reversedDigits n = go n

go 0 = []

go x = rem x 10 : go (quot x 10)

splitBy :: (a -> a -> Bool) -> [a] -> ([a], [a])

splitBy f xs = go $ break (uncurry f) $ zip xs (tail xs)

| null ys = ([], xs)

| otherwise = (fst (head ys) : map snd ys, map snd zs)

unDigits = foldl (\a b -> 10 * a + b) 0

fTable s xShow fxShow f xs =

unlines $

where

w = maximum (length . xShow <$> xs)

rjust :: Int -> Char -> String -> String

{{Out}}

<pre>Taking up to 5 digit-shuffle successors of a positive integer:

=={{header|Java}}==

Additional testing is performed, including a number with all unique digits and a number with duplicate digits. Included test of all permutations, that the order and correct number of permutations is achieved, and that each permutation is different than all others. If a library is not used, then this testing will provide a better proof of correctness.

import java.math.BigInteger;

import java.text.NumberFormat;

}

}

{{out}}

<pre>

</pre>

 

=={{header|Julia}}==

 

asint(dig) = foldl((i, j) -> 10i + Int128(j), dig)

@btime nexthighest_2(n)

println(" for method 2 and n $n.")

<pre>

N 1A 1B 2

for method 2 and n 7384440.

</pre>

 

=={{header|Perl}}==

{{trans|Raku}}

use warnings;

use feature 'say';

for (0, 9, 12, 21, 12453, 738440, 45072010, 95322020, 9589776899767587796600, 3345333) {

printf "%30s -> %s\n", comma($_), comma next_greatest_integer $_;

{{out}}

<pre> 0 -> 0

=={{header|Phix}}==

===algorithm 1===

{{out}}

<pre>

</pre>

===algorithm 2===

{{out}}

<pre>

===Python: Algorithm 2===

Like Algorithm 2, but digit order is reversed for easier indexing, then reversed on return.

"(index of) closest int from lst, to n that is also > n"

large = max(lst) + 1

for x in [0, 9, 12, 21, 12453, 738440, 45072010, 95322020,

9589776899767587796600]:

 

{{out}}

===Python: Algorithm 1===

I would not try it on the stretch goal, otherwise results as above.

 

 

if perm != this:

return int(''.join(perm))

 

===Python: Generator===

A variant which defines (in terms of a concatMap over permutations), a generator of '''all''' digit-shuffle successors for a given integer:

 

 

from itertools import chain, islice, permutations, tee

 

 

# digitShuffleSuccessors :: Int -> [Int]

def digitShuffleSuccessors(n):

successors of n, where 0 <= n.

'''

delta = int(''.join(ds)) - n

return [] if 0 >= delta else [delta]

 

 

# main :: IO ()

def main():

harvest = take(n)(ys)

return (

).rjust(12, ' ') + repr(harvest)

 

print(

 

 

 

# concatMap :: (a -> [b]) -> [a] -> [b]

def concatMap(f):

'''

 

 

# (b -> String) -> (a -> b) -> [a] -> String

def fTable(s):

'''

 

 

or xs itself if n > length xs.

'''

 

 

# MAIN ---

if __name__ == '__main__':

{{Out}}

<pre>Taking up to 5 digit-shuffle successors for each:

45072010 -> 5 of 1861: [45072100, 45100027, 45100072, 45100207, 45100270]

95322020 -> 1 of 1: [95322200]</pre>

 

=={{header|Raku}}==

Minimal error trapping. Assumes that the passed number is an integer. Handles positive or negative integers, always returns next largest regardless (if possible).

 

 

sub next-greatest-index ($str, &op = &infix:«<» ) {

printf "%30s -> %s%s\n", .&comma, .&next-greatest-integer < 0 ?? '' !! ' ', .&next-greatest-integer.&comma for

flat 0, (9, 12, 21, 12453, 738440, 45072010, 95322020, 9589776899767587796600, 3345333,

{{out}}

<pre>Next largest integer able to be made from these digits, or zero if no larger exists:

 

=={{header|REXX}}==

parse arg n /*obtain optional arguments from the CL*/

w= length( commas( word(n, words(n) ) ) ) /*maximum width number (with commas). */

 

exit /*stick a fork in it, we're all done. */

/*──────────────────────────────────────────────────────────────────────────────────────*/

/*──────────────────────────────────────────────────────────────────────────────────────*/

mask: parse arg z, $; @.= 0 /* [↓] build an unsorted digit mask. */

end /*k*/

do m=0 for 10; if @.m==0 then iterate; $= $ || copies(m, @.m)

{{out|output|text=&nbsp; when using the default inputs:}}

<pre>

for 45,072,010 ─── the next highest integer is: 45,072,100

for 95,322,020 ─── the next highest integer is: 95,322,200

</pre>

 

=={{header|Sidef}}==

 

var a = n.digits(b).flip

) {

printf("%30s -> %s\n", n, next_from_digits(n))

{{out}}

<pre>

982765431 -> 983124567

9589776899767587796600 -> 9589776899767587900667

</pre>

 

=={{header|zkl}}==

// ds:=N.split().copy(); // mutable, int

ds:=N.toString().split("").apply("toInt").copy(); // handle "234" or BigInt

}

"0"

foreach n in (ns){ println("%,d --> %,d".fmt(n,nextHightest(n))) }

 

n:="9589776899767587796600"; // or BigInt(n)

{{out}}

<pre>