Anonymous user
Next highest int from digits: Difference between revisions
→{{header|J}}
Thundergnat (talk | contribs) m (Fix Perl 6 -> Raku links) |
|||
Line 413:
45072010 45072100
95322020 95322200
</pre>
=={{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 correct number of permutations is achieved, and that each number is greater than the previous number. If a library is not used, then this testing will provide a better proof of correctness.
<lang java>
import java.math.BigInteger;
import java.text.NumberFormat;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class NextHighestIntFromDigits {
public static void main(String[] args) {
for ( String s : new String[] {"0", "9", "12", "21", "12453", "738440", "45072010", "95322020", "9589776899767587796600", "3345333"} ) {
System.out.printf("%s -> %s%n", format(s), format(next(s)));
}
testAll("12345");
testAll("11122");
}
private static NumberFormat FORMAT = NumberFormat.getNumberInstance();
private static String format(String s) {
return FORMAT.format(new BigInteger(s));
}
private static void testAll(String s) {
int count = 1;
System.out.printf("Test all iterations of: %s%n%d %s%n", s, count, format(s));
String sPrev = s;
while ( (s = next(s)).compareTo("0") != 0 ) {
count++;
System.out.printf("%d %s %s%n", count, format(s), Long.parseLong(s) > Long.parseLong(sPrev) ? "OK" : "NOT OK!!!");
sPrev = s;
}
}
private static String next(String s) {
StringBuilder sb = new StringBuilder();
int index = s.length()-1;
// 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.
while ( index > 0 && s.charAt(index-1) >= s.charAt(index)) {
index--;
}
// Reached beginning. No next number.
if ( index == 0 ) {
return "0";
}
// Find digit on the right that is both more than it, and closest to it.
int index2 = index;
for ( int i = index + 1 ; i < s.length() ; i++ ) {
if ( s.charAt(i) < s.charAt(index2) && s.charAt(i) > s.charAt(index-1) ) {
index2 = i;
}
}
// Found data, now build string
// Beginning of String
if ( index > 1 ) {
sb.append(s.subSequence(0, index-1));
}
// Append found, place next
sb.append(s.charAt(index2));
// Get remaining characters
List<Character> chars = new ArrayList<>();
chars.add(s.charAt(index-1));
for ( int i = index ; i < s.length() ; i++ ) {
if ( i != index2 ) {
chars.add(s.charAt(i));
}
}
// Order the digits to the right of this position, after the swap; lowest-to-highest, left-to-right.
Collections.sort(chars);
for ( char c : chars ) {
sb.append(c);
}
return sb.toString();
}
}
</lang>
{{out}}
<pre>
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
3,345,333 -> 3,353,334
Test all iterations of: 12345
1 12,345
2 12,354 OK
3 12,435 OK
4 12,453 OK
5 12,534 OK
... output removed to save space ...
119 54,312 OK
120 54,321 OK
Test all iterations of: 11122
1 11,122
2 11,212 OK
3 11,221 OK
4 12,112 OK
5 12,121 OK
6 12,211 OK
7 21,112 OK
8 21,121 OK
9 21,211 OK
10 22,111 OK
</pre>
| |||