Factorial base numbers indexing permutations of a collection: Difference between revisions
Content deleted Content added
Thundergnat (talk | contribs) m syntax highlighting fixup automation |
New post. |
||
Line 777: | Line 777: | ||
0 3 2 1 |
0 3 2 1 |
||
</pre> |
|||
=={{header|Java}}== |
|||
<syntaxhighlight lang="java"> |
|||
import java.util.ArrayList; |
|||
import java.util.Collections; |
|||
import java.util.List; |
|||
import java.util.concurrent.ThreadLocalRandom; |
|||
import java.util.stream.Collectors; |
|||
public final class FactorialBaseNumbersIndexingPermutations { |
|||
public static void main(String[] args) { |
|||
// Part 1 |
|||
List<Integer> elements = convertToListInteger("0.1.2.3"); |
|||
List<Integer> factoradic = convertToListInteger("0.0.0"); |
|||
for ( int i = 0; i < factorial(4); i++ ) { |
|||
List<Integer> rotated = permutation(elements, factoradic); |
|||
System.out.println(toString(factoradic, ".") + " --> " + toString(rotated, " ")); |
|||
increment(factoradic); |
|||
} |
|||
System.out.println(); |
|||
// Part 2 |
|||
System.out.println("Generating the permutations of 11 digits:"); |
|||
final int limit = factorial(11); |
|||
elements = convertToListInteger("0.1.2.3.4.5.6.7.8.9.10"); |
|||
factoradic = convertToListInteger("0.0.0.0.0.0.0.0.0.0"); |
|||
for ( int i = 0; i < limit; i++ ) { |
|||
List<Integer> rotated = permutation(elements, factoradic); |
|||
if ( i < 3 || i > limit - 4 ) { |
|||
System.out.println(toString(factoradic, ".") + " --> " + toString(rotated, " ")); |
|||
} else if ( i == 3 ) { |
|||
System.out.println(" [ ... ] "); |
|||
} |
|||
increment(factoradic); |
|||
} |
|||
System.out.println("Number of permutations is 11! = " + limit + System.lineSeparator()); |
|||
// Part 3. |
|||
List<String> codes = List.of( |
|||
"39.49.7.47.29.30.2.12.10.3.29.37.33.17.12.31.29.34.17.25.2.4.25.4.1.14" |
|||
+ ".20.6.21.18.1.1.1.4.0.5.15.12.4.3.10.10.9.1.6.5.5.3.0.0.0", |
|||
"51.48.16.22.3.0.19.34.29.1.36.30.12.32.12.29.30.26.14.21.8.12.1.3.10.4" |
|||
+ ".7.17.6.21.8.12.15.15.13.15.7.3.12.11.9.5.5.6.6.3.4.0.3.2.1" ); |
|||
List<String> cards = List.of( "A♠", "K♠", "Q♠", "J♠", "10♠", "9♠", "8♠", "7♠", "6♠", "5♠", "4♠", "3♠", "2♠", |
|||
"A♥", "K♥", "Q♥", "J♥", "10♥", "9♥", "8♥", "7♥", "6♥", "5♥", "4♥", "3♥", "2♥", |
|||
"A♦", "K♦", "Q♦", "J♦", "10♦", "9♦", "8♦", "7♦", "6♦", "5♦", "4♦", "3♦", "2♦", |
|||
"A♣", "K♣", "Q♣", "J♣", "10♣", "9♣", "8♣", "7♣", "6♣", "5♣", "4♣", "3♣", "2♣" ); |
|||
System.out.println("Original deck of cards:"); |
|||
System.out.println(toString(cards, " ") + System.lineSeparator()); |
|||
System.out.println("Task shuffles:"); |
|||
for ( String code : codes ) { |
|||
System.out.println(code + " --> "); |
|||
factoradic = convertToListInteger(code); |
|||
System.out.println(toString(permutation(cards, factoradic), " ")); |
|||
System.out.println(); |
|||
} |
|||
System.out.println("Random shuffle:"); |
|||
ThreadLocalRandom random = ThreadLocalRandom.current(); |
|||
factoradic.clear(); |
|||
for ( int i = 0; i < 52; i++ ) { |
|||
factoradic.add(random.nextInt(cards.size() - i)); |
|||
} |
|||
System.out.println(toString(factoradic, ".") + " --> "); |
|||
System.out.println(toString(permutation(cards, factoradic), " ")); |
|||
} |
|||
private static <T> List<T> permutation(List<T> elements, List<Integer> factorialBaseNumber) { |
|||
List<T> copy = new ArrayList<T>(elements); |
|||
int m = 0; |
|||
for ( int g : factorialBaseNumber ) { |
|||
Collections.rotate(copy.subList(m, m + g + 1), 1); |
|||
m += 1; |
|||
} |
|||
return copy; |
|||
} |
|||
private static void increment(List<Integer> factoradic) { |
|||
int index = factoradic.size() - 1; |
|||
while ( index >= 0 && factoradic.get(index) == factoradic.size() - index ) { |
|||
factoradic.set(index, 0); |
|||
index -= 1; |
|||
} |
|||
if ( index >= 0 ) { |
|||
factoradic.set(index, factoradic.get(index) + 1); |
|||
} |
|||
} |
|||
private static List<Integer> convertToListInteger(String text) { |
|||
List<Integer> result = new ArrayList<Integer>(); |
|||
String[] numbers = text.split("\\."); |
|||
for ( String number : numbers ) { |
|||
result.add(Integer.valueOf(number)); |
|||
} |
|||
return result; |
|||
} |
|||
private static int factorial(int n) { |
|||
int factorial = 1; |
|||
for ( int i = 2; i <= n; i++ ) { |
|||
factorial *= i; |
|||
} |
|||
return factorial; |
|||
} |
|||
private static <T> String toString(List<T> factoradic, String delimiter) { |
|||
return factoradic.stream().map(String::valueOf).collect(Collectors.joining(delimiter)); |
|||
} |
|||
} |
|||
</syntaxhighlight> |
|||
{{ out }} |
|||
<pre> |
|||
1.0.0 --> 1 0 2 3 |
|||
1.0.1 --> 1 0 3 2 |
|||
1.1.0 --> 1 2 0 3 |
|||
1.1.1 --> 1 2 3 0 |
|||
1.2.0 --> 1 3 0 2 |
|||
1.2.1 --> 1 3 2 0 |
|||
2.0.0 --> 2 0 1 3 |
|||
2.0.1 --> 2 0 3 1 |
|||
2.1.0 --> 2 1 0 3 |
|||
2.1.1 --> 2 1 3 0 |
|||
2.2.0 --> 2 3 0 1 |
|||
2.2.1 --> 2 3 1 0 |
|||
3.0.0 --> 3 0 1 2 |
|||
3.0.1 --> 3 0 2 1 |
|||
3.1.0 --> 3 1 0 2 |
|||
3.1.1 --> 3 1 2 0 |
|||
3.2.0 --> 3 2 0 1 |
|||
3.2.1 --> 3 2 1 0 |
|||
Generating the permutations of 11 digits: |
|||
0.0.0.0.0.0.0.0.0.0 --> 0 1 2 3 4 5 6 7 8 9 10 |
|||
0.0.0.0.0.0.0.0.0.1 --> 0 1 2 3 4 5 6 7 8 10 9 |
|||
0.0.0.0.0.0.0.0.1.0 --> 0 1 2 3 4 5 6 7 9 8 10 |
|||
[ ... ] |
|||
10.9.8.7.6.5.4.3.1.1 --> 10 9 8 7 6 5 4 3 1 2 0 |
|||
10.9.8.7.6.5.4.3.2.0 --> 10 9 8 7 6 5 4 3 2 0 1 |
|||
10.9.8.7.6.5.4.3.2.1 --> 10 9 8 7 6 5 4 3 2 1 0 |
|||
Number of permutations is 11! = 39916800 |
|||
Original deck of cards: |
|||
A♠ K♠ Q♠ J♠ 10♠ 9♠ 8♠ 7♠ 6♠ 5♠ 4♠ 3♠ 2♠ A♥ K♥ Q♥ J♥ 10♥ 9♥ 8♥ 7♥ 6♥ 5♥ 4♥ 3♥ 2♥ A♦ K♦ Q♦ J♦ 10♦ 9♦ 8♦ 7♦ 6♦ 5♦ 4♦ 3♦ 2♦ A♣ K♣ Q♣ J♣ 10♣ 9♣ 8♣ 7♣ 6♣ 5♣ 4♣ 3♣ 2♣ |
|||
Task shuffles: |
|||
39.49.7.47.29.30.2.12.10.3.29.37.33.17.12.31.29.34.17.25.2.4.25.4.1.14.20.6.21.18.1.1.1.4.0.5.15.12.4.3.10.10.9.1.6.5.5.3.0.0.0 --> |
|||
A♣ 3♣ 7♠ 4♣ 10♦ 8♦ Q♠ K♥ 2♠ 10♠ 4♦ 7♣ J♣ 5♥ 10♥ 10♣ K♣ 2♣ 3♥ 5♦ J♠ 6♠ Q♣ 5♠ K♠ A♦ 3♦ Q♥ 8♣ 6♦ 9♠ 8♠ 4♠ 9♥ A♠ 6♥ 5♣ 2♦ 7♥ 8♥ 9♣ 6♣ 7♦ A♥ J♦ Q♦ 9♦ 2♥ 3♠ J♥ 4♥ K♦ |
|||
51.48.16.22.3.0.19.34.29.1.36.30.12.32.12.29.30.26.14.21.8.12.1.3.10.4.7.17.6.21.8.12.15.15.13.15.7.3.12.11.9.5.5.6.6.3.4.0.3.2.1 --> |
|||
2♣ 5♣ J♥ 4♥ J♠ A♠ 5♥ A♣ 6♦ Q♠ 9♣ 3♦ Q♥ J♣ 10♥ K♣ 10♣ 5♦ 7♥ 10♦ 3♠ 8♥ 10♠ 7♠ 6♥ 5♠ K♥ 4♦ A♥ 4♣ 2♥ 9♦ Q♣ 8♣ 7♦ 6♣ 3♥ 6♠ 7♣ 2♦ J♦ 9♥ A♦ Q♦ 8♦ 4♠ K♦ K♠ 3♣ 2♠ 8♠ 9♠ |
|||
Random shuffle: |
|||
24.45.8.6.12.29.39.31.8.0.25.27.27.5.29.32.4.31.0.1.27.22.3.13.22.13.11.17.7.8.12.5.19.18.10.2.9.12.7.2.6.9.7.6.0.2.2.1.1.0.1.0 --> |
|||
3♥ 7♣ 6♠ 8♠ K♥ 7♦ 9♣ 4♦ 4♠ A♠ 9♦ 5♦ 3♦ 7♠ Q♣ 6♣ 9♠ 5♣ K♠ J♠ 10♣ 6♦ 3♠ 4♥ K♣ 2♥ 6♥ 8♦ 10♥ 8♥ Q♦ Q♥ 2♣ 3♣ K♦ 5♠ J♦ J♣ 5♥ 2♠ A♦ 8♣ 2♦ 10♦ Q♠ J♥ 9♥ A♥ 7♥ 10♠ 4♣ A♣ |
|||
</pre> |
</pre> |
||