Next highest int from digits: Difference between revisions
Added Go
m (→{{header|Factor}}: English is harder than code sometimes) |
(Added Go) |
||
Line 85:
95322020 -> 95322200
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.
<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>
{{out}}
<pre>
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
</pre>
| |||