fork download
copy 
  1. import java.math.BigInteger;
  2. import java.util.Arrays;
  3. import java.util.Collections;
  4. import java.util.List;
  5. import java.util.Objects;
  6. import java.util.stream.Collectors;
  7. import java.util.stream.IntStream;
  8. import java.util.stream.Stream;
  9.  
  10. class Permutations {
  11.  
  12. 	public static void main(String[] args) {
  13. 		var permutationA = new Permutation<>(1, 2, 3, 4, 5, 6, 7, 8, 9);
  14. 		System.out.println(permutationA.get(new BigInteger("1")));
  15. 		System.out.println(permutationA.get(new BigInteger("2")));
  16. 		System.out.println(permutationA.get(new BigInteger("3")));
  17. 		System.out.println(permutationA.get(new BigInteger("123456")));
  18. 		System.out.println(permutationA.get(new BigInteger("234567")));
  19. 		System.out.println(permutationA.get(new BigInteger("362880")));
  20. 		var permutationB = new Permutation<>(1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4);
  21. 		System.out.println(permutationB.get(new BigInteger("1")));
  22. 		System.out.println(permutationB.get(new BigInteger("2")));
  23. 		System.out.println(permutationB.get(new BigInteger("3")));
  24. 		System.out.println(permutationB.get(new BigInteger("123456")));
  25. 		System.out.println(permutationB.get(new BigInteger("234567")));
  26. 		System.out.println(permutationB.get(new BigInteger("369600")));
  27. 	}
  28.  
  29. 	static class Permutation<T extends Comparable<T>> {
  30. 		private final List<T> valueList;
  31. 		private final List<T> distinctValueList;
  32. 		private final int[] distinctValueCounts;
  33. 		@SuppressWarnings("unchecked")
  34. 		Permutation(T... values) {
  35. 			Objects.requireNonNull(values);
  36. //			valueList = Arrays.stream(values).sorted().toList();
  37. 			valueList = Collections.unmodifiableList(Arrays.stream(values).sorted().collect(Collectors.toList()));
  38. //			distinctValueList = valueList.stream().distinct().toList();
  39. 			distinctValueList = Collections.unmodifiableList(valueList.stream().distinct().collect(Collectors.toList()));
  40. 			distinctValueCounts = distinctValueList.stream()
  41. 					.flatMap(x -> Stream.of(valueList.stream().filter(value -> value.equals(x)).count()))
  42. 					.mapToInt(count -> count.intValue())
  43. 					.toArray();
  44. 		}
  45. 		List<T> get(BigInteger index) {
  46. 			var numberOfPermutations = numberOfPermutations(distinctValueCounts);
  47. 			if (index.compareTo(BigInteger.ONE) < 0 || index.compareTo(numberOfPermutations) > 0) {
  48. 				throw new IllegalArgumentException("Requires index >= 1 && index <= " + numberOfPermutations + ", but index = " + index);
  49. 			}
  50. 			var states = new Object() {
  51. 				BigInteger index;
  52. 				int[] distinctValueCounts;
  53. 				void setIndex(BigInteger index) {
  54. 					this.index = index.subtract(BigInteger.ONE);
  55. 				}
  56. 				void setDistinctValueCounts(int[] distinctValueCounts) {
  57. 					this.distinctValueCounts = distinctValueCounts;
  58. 				}
  59. 				NumberOfPermutationsTableData[] numberOfPermutationsTable;
  60. 				BigInteger iTableValueMax;
  61. 				void reset() {
  62. 					numberOfPermutationsTable = getNumberOfPermutationsTable(distinctValueCounts);
  63. 					iTableValueMax = BigInteger.ZERO;
  64. 				}
  65. 				void setNextDistionctValuecounts(int iNumberOfPermutationsTable) {
  66. 					distinctValueCounts = numberOfPermutationsTable[iNumberOfPermutationsTable].distinctValueCounts;
  67. 				}
  68. 				boolean compare(int iNumberOfPermutationsTable) {
  69. 					var iTableValueMax = this.iTableValueMax.add(numberOfPermutationsTable[iNumberOfPermutationsTable].numberOfPermutations);
  70. 					if (index.compareTo(iTableValueMax) < 0) {
  71. 						index = index.subtract(this.iTableValueMax);
  72. 						return true;
  73. 					}
  74. 					this.iTableValueMax = iTableValueMax;
  75. 					return false;
  76. 				}
  77. 			};
  78. 			states.setIndex(index);
  79. 			states.setDistinctValueCounts(distinctValueCounts);
  80. 			return IntStream.range(0, valueList.size())
  81. 					.mapToObj(iResultList -> {
  82. 						states.reset();
  83. 						var iNumberOfPermutationsTableOptional = IntStream.range(0, states.numberOfPermutationsTable.length)
  84. 								.filter(iNumberOfPermutationsTable -> states.compare(iNumberOfPermutationsTable))
  85. 								.findFirst();
  86. 						if (iResultList < valueList.size() - 1) {
  87. 							states.setNextDistionctValuecounts(iNumberOfPermutationsTableOptional.getAsInt());
  88. 						}
  89. 						return distinctValueList.get(iNumberOfPermutationsTableOptional.getAsInt());
  90. 					})
  91. //					.toList();
  92. 					.collect(Collectors.toList());
  93. 		}
  94. 		private int[] newDistinctValueCounts(int[] distinctValueCounts, int indexOfArrayToDecrement) {
  95. 			var clone = distinctValueCounts.clone();
  96. 			--clone[indexOfArrayToDecrement];
  97. 			return clone;
  98. 		}
  99. 		static class NumberOfPermutationsTableData {
  100. 			final BigInteger numberOfPermutations;
  101. 			final int[] distinctValueCounts;
  102. 			NumberOfPermutationsTableData(BigInteger numberOfPermutations, int[] distinctValueCounts) {
  103. 				this.numberOfPermutations = numberOfPermutations;
  104. 				this.distinctValueCounts = distinctValueCounts;
  105. 			}
  106. 		}
  107. 		private NumberOfPermutationsTableData[] getNumberOfPermutationsTable(int[] distinctValueCounts) {
  108. 			return IntStream.range(0, distinctValueCounts.length)
  109. 					.mapToObj(index -> {
  110. 						var newDistinctValueCounts = newDistinctValueCounts(distinctValueCounts, index);
  111. 						var numberOfPermutations = numberOfPermutations(newDistinctValueCounts);
  112. 						return new NumberOfPermutationsTableData(numberOfPermutations, newDistinctValueCounts);
  113. 					})
  114. 					.toArray(NumberOfPermutationsTableData[]::new);
  115. 		}
  116. 		private BigInteger numberOfPermutations(int[] distinctValueCounts) {
  117. 			if (Arrays.stream(distinctValueCounts).filter(count -> count < 0).findFirst().isPresent()) {
  118. 				return BigInteger.ZERO;
  119. 			}
  120. 			return factorial(Arrays.stream(distinctValueCounts).reduce(0, (a, b) -> a + b))
  121. 					.divide(Arrays.stream(distinctValueCounts)
  122. 							.mapToObj(this::factorial)
  123. 							.reduce(BigInteger.ONE, (a, b) -> a.multiply(b)));
  124. 		}
  125. 		private BigInteger factorial(int n) {
  126. 			if (n == 0) {
  127. 				return BigInteger.ONE;
  128. 			}
  129. 			if (n < 1) {
  130. 				throw new IllegalArgumentException("Requires n >= 1 && n <= " + Integer.MAX_VALUE + ", but n = " + n);
  131. 			}
  132. 			return IntStream.rangeClosed(1, n).mapToObj(BigInteger::valueOf).reduce(BigInteger.ONE, (a, b) -> a.multiply(b));
  133. 		}
  134. 	}
  135.  
  136. }
  137.  
Success #stdin #stdout 0.25s 60652KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
[1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 2, 3, 4, 5, 6, 7, 9, 8]
[1, 2, 3, 4, 5, 6, 8, 7, 9]
[4, 1, 6, 5, 8, 9, 7, 3, 2]
[6, 8, 4, 7, 5, 3, 2, 1, 9]
[9, 8, 7, 6, 5, 4, 3, 2, 1]
[1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4]
[1, 1, 1, 2, 2, 2, 3, 3, 4, 3, 4, 4]
[1, 1, 1, 2, 2, 2, 3, 3, 4, 4, 3, 4]
[2, 2, 2, 3, 3, 1, 4, 3, 4, 1, 1, 4]
[3, 2, 4, 4, 2, 4, 3, 3, 1, 1, 1, 2]
[4, 4, 4, 3, 3, 3, 2, 2, 2, 1, 1, 1]
https://ideone.com/qRTy1Z
language:
Java (12.0.1)
created:
28 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!