Next highest int from digits: Difference between revisions
m (→{{header|REXX}}: simplified code for inner DO loop.) |
|||
Line 277: | Line 277: | ||
return int(''.join(perm)) |
return int(''.join(perm)) |
||
return 0</lang> |
return 0</lang> |
||
===Python: Generator=== |
|||
A variant which defines, in terms of concatMap, a generator of '''all''' digit-shuffle successors for a given integer: |
|||
<lang python>'''Digit-shuffle successors''' |
|||
from itertools import chain, islice, permutations |
|||
# digitShuffleSuccessors :: Int -> [Int] |
|||
def digitShuffleSuccessors(n): |
|||
'''Generator stream of all digit-shuffle |
|||
successors of n, where 0 <= n. |
|||
''' |
|||
def go(ds): |
|||
delta = int(''.join(list(ds))) - n |
|||
return [] if 0 >= delta else [delta] |
|||
for x in sorted(list(set(concatMap(go)( |
|||
list(permutations(str(n))) |
|||
)))): |
|||
yield n + x |
|||
# TEST ---------------------------------------------------- |
|||
# main :: IO () |
|||
def main(): |
|||
'''Up to 5 digit shuffle sucessors for each:''' |
|||
print( |
|||
fTable(main.__doc__)(str)(str)( |
|||
lambda n: take(5)(digitShuffleSuccessors(n)) |
|||
)([ |
|||
0, |
|||
9, |
|||
12, |
|||
21, |
|||
12453, |
|||
738440, |
|||
45072010 |
|||
]) |
|||
) |
|||
# GENERIC ------------------------------------------------- |
|||
# concatMap :: (a -> [b]) -> [a] -> [b] |
|||
def concatMap(f): |
|||
'''A concatenated list or string over which a function f |
|||
has been mapped. |
|||
The list monad can be derived by using an (a -> [b]) |
|||
function which wraps its output in a list (using an |
|||
empty list to represent computational failure). |
|||
''' |
|||
return lambda xs: chain.from_iterable(map(f, xs)) |
|||
# fTable :: String -> (a -> String) -> |
|||
# (b -> String) -> (a -> b) -> [a] -> String |
|||
def fTable(s): |
|||
'''Heading -> x display function -> fx display function -> |
|||
f -> xs -> tabular string. |
|||
''' |
|||
def go(xShow, fxShow, f, xs): |
|||
ys = [xShow(x) for x in xs] |
|||
w = max(map(len, ys)) |
|||
return s + '\n' + '\n'.join(map( |
|||
lambda x, y: y.rjust(w, ' ') + ' -> ' + fxShow(f(x)), |
|||
xs, ys |
|||
)) |
|||
return lambda xShow: lambda fxShow: lambda f: lambda xs: go( |
|||
xShow, fxShow, f, xs |
|||
) |
|||
# take :: Int -> [a] -> [a] |
|||
# take :: Int -> String -> String |
|||
def take(n): |
|||
'''The prefix of xs of length n, |
|||
or xs itself if n > length xs. |
|||
''' |
|||
return lambda xs: ( |
|||
xs[0:n] |
|||
if isinstance(xs, (list, tuple)) |
|||
else list(islice(xs, n)) |
|||
) |
|||
# MAIN --- |
|||
if __name__ == '__main__': |
|||
main()</lang> |
|||
{{Out}} |
|||
<pre>Up to 5 digit shuffle sucessors for each: |
|||
0 -> [] |
|||
9 -> [] |
|||
12 -> [21] |
|||
21 -> [] |
|||
12453 -> [12534, 12543, 13245, 13254, 13425] |
|||
738440 -> [740348, 740384, 740438, 740483, 740834] |
|||
45072010 -> [45072100, 45100027, 45100072, 45100207, 45100270]</pre> |
|||
=={{header|REXX}}== |
=={{header|REXX}}== |
Revision as of 17:01, 22 February 2020
Given a zero or positive integer, the task is to generate the next largest integer using only the given digits*1.
- Numbers will not be padded to the left with zeroes.
- Use all given digits, with their given multiplicity. (If a digit appears twice in the input number, it should appear twice in the result).
- If there is no next higest integer return zero.
*1 Alternatively phrased as: "Find the smallest integer larger than the (positive or zero) integer N which can be obtained by reordering the (base 10) digits of N".
- Algorithm 1
- Generate all the permutations of the digits and sort into numeric order.
- Find the number in the list.
- Return the next highest number from the list.
The above could prove slow and memory hungry for numbers with large numbers of digits, but should be easy to reason about its correctness.
- Algorithm 2
- Scan right-to-left through the digits of the number until you find a digit with a larger digit somewhere to the right of it.
- Exchange that digit with the digit on the right that is both more than it, and closest to it.
- Order the digits to the right of this position, after the swap; lowest-to-highest, left-to-right. (I.e. so they form the lowest numerical representation)
E.g:
n = 12453 <scan> 12_4_53 <swap> 12_5_43 <order-right> 12_5_34 return: 12534
This second algorithm is faster and more memory efficient, but implementations may be harder to test. One method of testing ,(as used in developing the task), is to compare results from both algorithms for random numbers generated from a range that the first algorithm can handle.
- Task requirements
Calculate the next highest int from the digits of the following numbers:
- 0
- 9
- 12
- 21
- 12453
- 738440
- 45072010
- 95322020
- Optional stretch goal
- 9589776899767587796600
Factor
This uses the next-permutation
word from the math.combinatorics
vocabulary. next-permutation
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 next-permutation
here.
<lang factor>USING: formatting grouping kernel math math.combinatorics math.parser sequences ;
- next-highest ( m -- n )
number>string dup [ >= ] monotonic? [ drop 0 ] [ next-permutation string>number ] if ;
{
0 9 12 21 12453 738440 45072010 95322020 9589776899767587796600
} [ dup next-highest "%d -> %d\n" printf ] each</lang>
- Output:
0 -> 0 9 -> 0 12 -> 21 21 -> 0 12453 -> 12534 738440 -> 740348 45072010 -> 45072100 95322020 -> 95322200 9589776899767587796600 -> 9589776899767587900667
Go
This uses a modified version of the recursive code in the [Permutations#Go] task. <lang go>package main
import (
"fmt" "sort"
)
func permute(s string) []string {
var res []string if len(s) == 0 { return res } b := []byte(s) var rc func(int) // recursive closure rc = func(np int) { if np == 1 { res = append(res, string(b)) return } np1 := np - 1 pp := len(b) - np1 rc(np1) for i := pp; i > 0; i-- { b[i], b[i-1] = b[i-1], b[i] rc(np1) } w := b[0] copy(b, b[1:pp+1]) b[pp] = w } rc(len(b)) return res
}
func commatize(s string) string {
le := len(s) for i := le - 3; i >= 1; i -= 3 { s = s[0:i] + "," + s[i:] } return s
}
func main() {
nums := []string{"0", "9", "12", "21", "12453", "738440", "45072010", "95322020", "9589776899767587796600"} fmt.Println("Algorithm 1") fmt.Println("-----------") for _, num := range nums[:len(nums)-1] { // exclude the last one perms := permute(num) le := len(perms) if le == 0 { // ignore blanks continue } sort.Strings(perms) ix := sort.SearchStrings(perms, num) next := "" if ix < le-1 { for i := ix + 1; i < le; i++ { if perms[i] > num { next = perms[i] break } } } if len(next) > 0 { fmt.Printf(" %s -> %s\n", commatize(num), commatize(next)) } else { fmt.Printf(" %s -> 0\n", commatize(num)) } } fmt.Println() fmt.Println("Algorithm 2") fmt.Println("-----------")
outer:
for _, num := range nums { // include the last one b := []byte(num) le := len(b) if le == 0 { // ignore blanks continue } max := num[le-1] mi := le - 1 for i := le - 2; i >= 0; i-- { if b[i] < max { min := max - b[i] for j := mi + 1; j < le; j++ { min2 := b[j] - b[i] if min2 > 0 && min2 < min { min = min2 mi = j } } b[i], b[mi] = b[mi], b[i] c := b[i+1:] d := permute(string(c)) sort.Strings(d) next := string(b[0:i+1]) + string(d[0]) fmt.Printf(" %s -> %s\n", commatize(num), commatize(next)) continue outer } else { max = num[i] mi = i } } fmt.Printf(" %s -> 0\n", commatize(num)) }
}</lang>
- Output:
Algorithm 1 ----------- 0 -> 0 9 -> 0 12 -> 21 21 -> 0 12,453 -> 12,534 738,440 -> 740,348 45,072,010 -> 45,072,100 95,322,020 -> 95,322,200 Algorithm 2 ----------- 0 -> 0 9 -> 0 12 -> 21 21 -> 0 12,453 -> 12,534 738,440 -> 740,348 45,072,010 -> 45,072,100 95,322,020 -> 95,322,200 9,589,776,899,767,587,796,600 -> 9,589,776,899,767,587,900,667
Python
Python: Algorithm 2
Like Algorithm 2, but digit order is reversed for easier indexing, then reversed on return. <lang python>def closest_more_than(n, lst):
"(index of) closest int from lst, to n that is also > n" large = max(lst) + 1 return lst.index(min(lst, key=lambda x: (large if x <= n else x)))
def nexthigh(n):
"Return nxt highest number from n's digits using scan & re-order" assert n == int(abs(n)), "n >= 0" this = list(int(digit) for digit in str(int(n)))[::-1] mx = this[0] for i, digit in enumerate(this[1:], 1): if digit < mx: mx_index = closest_more_than(digit, this[:i + 1]) this[mx_index], this[i] = this[i], this[mx_index] this[:i] = sorted(this[:i], reverse=True) return int(.join(str(d) for d in this[::-1])) elif digit > mx: mx, mx_index = digit, i return 0
if __name__ == '__main__':
for x in [0, 9, 12, 21, 12453, 738440, 45072010, 95322020, 9589776899767587796600]: print(f"{x:>12_d} -> {nexthigh(x):>12_d}")</lang>
- Output:
Note underscores are used in integer representations to aid in comparisons.
0 -> 0 9 -> 0 12 -> 21 21 -> 0 12_453 -> 12_534 738_440 -> 740_348 45_072_010 -> 45_072_100 95_322_020 -> 95_322_200 9_589_776_899_767_587_796_600 -> 9_589_776_899_767_587_900_667
Python: Algorithm 1
I would not try it on the stretch goal, otherwise results as above. <lang python>from itertools import permutations
def nexthigh(n):
"Return next highest number from n's digits using search of all digit perms" assert n == int(abs(n)), "n >= 0" this = tuple(str(int(n))) perms = sorted(permutations(this)) for perm in perms[perms.index(this):]: if perm != this: return int(.join(perm)) return 0</lang>
Python: Generator
A variant which defines, in terms of concatMap, a generator of all digit-shuffle successors for a given integer:
<lang python>Digit-shuffle successors
from itertools import chain, islice, permutations
- digitShuffleSuccessors :: Int -> [Int]
def digitShuffleSuccessors(n):
Generator stream of all digit-shuffle successors of n, where 0 <= n. def go(ds): delta = int(.join(list(ds))) - n return [] if 0 >= delta else [delta] for x in sorted(list(set(concatMap(go)( list(permutations(str(n))) )))): yield n + x
- TEST ----------------------------------------------------
- main :: IO ()
def main():
Up to 5 digit shuffle sucessors for each:
print( fTable(main.__doc__)(str)(str)( lambda n: take(5)(digitShuffleSuccessors(n)) )([ 0, 9, 12, 21, 12453, 738440, 45072010 ]) )
- GENERIC -------------------------------------------------
- concatMap :: (a -> [b]) -> [a] -> [b]
def concatMap(f):
A concatenated list or string over which a function f has been mapped. The list monad can be derived by using an (a -> [b]) function which wraps its output in a list (using an empty list to represent computational failure). return lambda xs: chain.from_iterable(map(f, xs))
- fTable :: String -> (a -> String) ->
- (b -> String) -> (a -> b) -> [a] -> String
def fTable(s):
Heading -> x display function -> fx display function -> f -> xs -> tabular string. def go(xShow, fxShow, f, xs): ys = [xShow(x) for x in xs] w = max(map(len, ys)) return s + '\n' + '\n'.join(map( lambda x, y: y.rjust(w, ' ') + ' -> ' + fxShow(f(x)), xs, ys )) return lambda xShow: lambda fxShow: lambda f: lambda xs: go( xShow, fxShow, f, xs )
- take :: Int -> [a] -> [a]
- take :: Int -> String -> String
def take(n):
The prefix of xs of length n, or xs itself if n > length xs. return lambda xs: ( xs[0:n] if isinstance(xs, (list, tuple)) else list(islice(xs, n)) )
- MAIN ---
if __name__ == '__main__':
main()</lang>
- Output:
Up to 5 digit shuffle sucessors for each: 0 -> [] 9 -> [] 12 -> [21] 21 -> [] 12453 -> [12534, 12543, 13245, 13254, 13425] 738440 -> [740348, 740384, 740438, 740483, 740834] 45072010 -> [45072100, 45100027, 45100072, 45100207, 45100270]
REXX
<lang rexx>/*REXX program finds the next highest positive integer from a list of decimal digits. */ parse arg n /*obtain optional arguments from the CL*/ if n= | n="," then n= 0 9 12 21 12453 738440 45072010 95322020 /*use the defaults? */ w= length( commas( word(n, words(n) ) ) ) /*maximum width number (with commas). */
do j=1 for words(n); y= word(n, j) /*process each of the supplied numbers.*/ masky= mask(y) /*build a digit mask for a supplied int*/ lim= copies(9, length(y) ) /*construct a LIMIT for the DO loop. */
do #=y+1 to lim until mask(#)==masky /*search for a number that might work. */ if verify(y, #) \== 0 then iterate /*does # have all the necessary digits?*/ end /*#*/
if #>lim then #= 0 /*if # > lim, then there is no valid #*/ say 'for ' right(commas(y),w) " ─── the next highest integer is: " right(commas(#),w) end /*j*/
exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ commas: parse arg _; do c=length(_)-3 to 1 by -3; _=insert(',', _, c); end; return _ /*──────────────────────────────────────────────────────────────────────────────────────*/ mask: parse arg z, $; @.= 0 /* [↓] build an unsorted digit mask. */
do k=1 for length(z); parse var z _ +1 z; @._= @._ + 1 end /*k*/ do m=0 for 10; if @.m==0 then iterate; $= $ || copies(m, @.m) end /*m*/; return $ /* [↑] build a sorted digit mask.*/</lang>
- output when using the default inputs:
for 0 ─── the next highest integer is: 0 for 9 ─── the next highest integer is: 0 for 12 ─── the next highest integer is: 21 for 21 ─── the next highest integer is: 0 for 12,453 ─── the next highest integer is: 12,534 for 738,440 ─── the next highest integer is: 740,348 for 45,072,010 ─── the next highest integer is: 45,072,100 for 95,322,020 ─── the next highest integer is: 95,322,200