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