fork(7) download
copy 
  1. /*
  2.  * This code demonstrates a solution to the problem described at
  3.  * https://stackoverflow.com/questions/61393463/
  4.  * Copyright (c) 2020, John McClane. All rights reserved.
  5.  *   
  6.  */
  7.  
  8. import java.util.*;
  9. import java.util.function.Supplier;
  10. import java.util.function.BiConsumer;
  11. import java.math.BigInteger;
  12.  
  13. abstract class PartitionGenerator implements Supplier<int[]>{
  14. 	public static final Random rand = new Random();
  15. 	protected final int numberCount;
  16. 	protected final int min;
  17. 	protected final int range;
  18. 	protected final int sum; // shifted sum
  19. 	protected final boolean sorted;
  20.  
  21. 	protected PartitionGenerator(int numberCount, int min, int max, int sum, boolean sorted) {
  22. 		if (numberCount <= 0)
  23. 			throw new IllegalArgumentException("Number count should be positive");
  24. 		this.numberCount = numberCount;
  25. 		this.min = min;
  26. 		range = max - min;
  27. 		if (range < 0)
  28. 			throw new IllegalArgumentException("min > max");
  29. 		sum -= numberCount * min;
  30. 		if (sum < 0)
  31. 			throw new IllegalArgumentException("Sum is too small");
  32. 		if (numberCount * range < sum)
  33. 			throw new IllegalArgumentException("Sum is too large");
  34. 		this.sum = sum;
  35. 		this.sorted = sorted;
  36. 	}
  37.  
  38. 	// Whether this generator returns sorted arrays (i.e. combinations)
  39. 	public final boolean isSorted() {
  40. 		return sorted;
  41. 	}
  42.  
  43. 	public interface GeneratorFactory {
  44. 		PartitionGenerator create(int numberCount, int min, int max, int sum);
  45. 	}
  46. }
  47.  
  48. // Permutations with repetition (i.e. unsorted vectors) with given sum
  49. class PermutationPartitionGenerator extends PartitionGenerator {
  50. 	private final double[][] distributionTable;
  51.  
  52. 	public PermutationPartitionGenerator(int numberCount, int min, int max, int sum) {
  53. 		super(numberCount, min, max, sum, false);
  54. 		distributionTable = calculateSolutionCountTable();
  55. 	}
  56.  
  57. 	private double[][] calculateSolutionCountTable() {
  58. 		double[][] table = new double[numberCount + 1][sum + 1];
  59. 		BigInteger[] a = new BigInteger[sum + 1];
  60. 		BigInteger[] b = new BigInteger[sum + 1];
  61. 		for (int i = 1; i <= sum; i++)
  62. 			a[i] = BigInteger.ZERO;
  63. 		a[0] = BigInteger.ONE;
  64. 		table[0][0] = 1.0;
  65. 		for (int n = 1; n <= numberCount; n++) {
  66. 			double[] t = table[n];
  67. 			for (int s = 0; s <= sum; s++) {
  68. 				BigInteger z = BigInteger.ZERO;
  69. 				for (int i = Math.max(0, s - range); i <= s; i++)
  70. 					z = z.add(a[i]);
  71. 				b[s] = z;
  72. 				t[s] = z.doubleValue();
  73. 			}
  74. 			// swap a and b
  75. 			BigInteger[] c = b;
  76. 			b = a;
  77. 			a = c;
  78. 		}
  79. 		return table;
  80. 	}
  81.  
  82. 	@Override
  83. 	public int[] get() {
  84. 		int[] p = new int[numberCount];
  85. 		int s = sum; // current sum
  86. 		for (int i = numberCount - 1; i >= 0; i--) {
  87. 			double t = rand.nextDouble() * distributionTable[i + 1][s];
  88. 			double[] tableRow = distributionTable[i];
  89. 			int oldSum = s;
  90. 			// lowerBound is introduced only for safety, it shouldn't be crossed 
  91. 			int lowerBound = s - range;
  92. 			if (lowerBound < 0)
  93. 				lowerBound = 0;
  94. 			s++;
  95. 			do
  96. 				t -= tableRow[--s];
  97. 			// s can be equal to lowerBound here with t > 0 only due to imprecise subtraction
  98. 			while (t > 0 && s > lowerBound);
  99. 			p[i] = min + (oldSum - s);
  100. 		}
  101. 		assert s == 0;
  102. 		return p;
  103. 	}
  104.  
  105. 	public static final PartitionGenerator.GeneratorFactory factory = (numberCount, min, max,sum) ->
  106. 		new PermutationPartitionGenerator(numberCount, min, max, sum);
  107. }
  108.  
  109. // Combinations with repetition (i.e. sorted vectors) with given sum 
  110. class CombinationPartitionGenerator extends PartitionGenerator {
  111. 	private final double[][][] distributionTable;
  112.  
  113. 	public CombinationPartitionGenerator(int numberCount, int min, int max, int sum) {
  114. 		super(numberCount, min, max, sum, true);
  115. 		distributionTable = calculateSolutionCountTable();
  116. 	}
  117.  
  118. 	private double[][][] calculateSolutionCountTable() {
  119. 		double[][][] table = new double[numberCount + 1][range + 1][sum + 1];
  120. 		BigInteger[][] a = new BigInteger[range + 1][sum + 1];
  121. 		BigInteger[][] b = new BigInteger[range + 1][sum + 1];
  122. 		double[][] t = table[0];
  123. 		for (int m = 0; m <= range; m++) {
  124. 			a[m][0] = BigInteger.ONE;
  125. 			t[m][0] = 1.0;
  126. 			for (int s = 1; s <= sum; s++) {
  127. 				a[m][s] = BigInteger.ZERO;
  128. 				t[m][s] = 0.0;
  129. 			}
  130. 		}
  131. 		for (int n = 1; n <= numberCount; n++) {
  132. 			t = table[n];
  133. 			for (int m = 0; m <= range; m++)
  134. 				for (int s = 0; s <= sum; s++) {
  135. 					BigInteger z;
  136. 					if (m == 0)
  137. 						z = a[0][s];
  138. 					else {
  139. 						z = b[m - 1][s];
  140. 						if (m <= s)
  141. 							z = z.add(a[m][s - m]);
  142. 					}
  143. 					b[m][s] = z;
  144. 					t[m][s] = z.doubleValue();
  145. 				}
  146. 			// swap a and b
  147. 			BigInteger[][] c = b;
  148. 			b = a;
  149. 			a = c;
  150. 		}
  151. 		return table;
  152. 	}
  153.  
  154. 	@Override
  155. 	public int[] get() {
  156. 		int[] p = new int[numberCount];
  157. 		int m = range; // current max
  158. 		int s = sum; // current sum
  159. 		for (int i = numberCount - 1; i >= 0; i--) {
  160. 			double t = rand.nextDouble() * distributionTable[i + 1][m][s];
  161. 			double[][] tableCut = distributionTable[i];
  162. 			if (s < m)
  163. 				m = s;
  164. 			s -= m;
  165. 			while (true) {
  166. 				t -= tableCut[m][s];
  167. 				// m can be 0 here with t > 0 only due to imprecise subtraction
  168. 				if (t <= 0 || m == 0)
  169. 					break;
  170. 				m--;
  171. 				s++;
  172. 			}
  173. 			p[i] = min + m;
  174. 		}
  175. 		assert s == 0;
  176. 		return p;
  177. 	}
  178.  
  179. 	public static final PartitionGenerator.GeneratorFactory factory = (numberCount, min, max, sum) ->
  180. 		new CombinationPartitionGenerator(numberCount, min, max, sum);
  181. }
  182.  
  183. class SmithTromblePartitionGenerator extends PartitionGenerator {
  184. 	public SmithTromblePartitionGenerator(int numberCount, int min, int max, int sum) {
  185. 		super(numberCount, min, max, sum, false);
  186. 	}
  187.  
  188. 	@Override
  189. 	public int[] get() {
  190. 		List<Integer> ls = new ArrayList<>(numberCount + 1);
  191. 		int[] ret = new int[numberCount];
  192. 		int increasedSum = sum + numberCount;
  193. 		while (true) {
  194. 			ls.add(0);
  195. 			while (ls.size() < numberCount) {
  196. 				int c = 1 + rand.nextInt(increasedSum - 1);
  197. 				if (!ls.contains(c))
  198. 					ls.add(c);
  199. 			}
  200. 			Collections.sort(ls);
  201. 			ls.add(increasedSum);
  202. 			boolean good = true;
  203. 			for (int i = 0; i < numberCount; i++) {
  204. 				int x = ls.get(i + 1) - ls.get(i) - 1;
  205. 				if (x > range) {
  206. 					good = false;
  207. 					break;
  208. 				}
  209. 				ret[i] = x;
  210. 			}
  211. 			if (good) {
  212. 				for (int i = 0; i < numberCount; i++)
  213. 					ret[i] += min;
  214. 				return ret;
  215. 			}
  216. 			ls.clear();
  217. 		}
  218. 	}
  219.  
  220. 	public static final PartitionGenerator.GeneratorFactory factory = (numberCount, min, max, sum) ->
  221. 		new SmithTromblePartitionGenerator(numberCount, min, max, sum);
  222. }
  223.  
  224. // Enumerates all partitions with given parameters
  225. class SequentialEnumerator extends PartitionGenerator {
  226. 	private final int max;
  227. 	private final int[] p;
  228. 	private boolean finished;
  229.  
  230. 	public SequentialEnumerator(int numberCount, int min, int max, int sum, boolean sorted) {
  231. 		super(numberCount, min, max, sum, sorted);
  232. 		this.max = max;
  233. 		p = new int[numberCount];
  234. 		startOver();
  235. 	}
  236.  
  237. 	private void startOver() {
  238. 		finished = false;
  239. 		int unshiftedSum = sum + numberCount * min;
  240. 		fillMinimal(0, Math.max(min, unshiftedSum - (numberCount - 1) * max), unshiftedSum);
  241. 	}
  242.  
  243. 	private void fillMinimal(int beginIndex, int minValue, int fillSum) {
  244. 		int fillRange = max - minValue;
  245. 		if (fillRange == 0)
  246. 			Arrays.fill(p, beginIndex, numberCount, max);
  247. 		else {
  248. 			int fillCount = numberCount - beginIndex;
  249. 			fillSum -= fillCount * minValue;
  250. 			int maxCount = fillSum / fillRange;
  251. 			int maxStartIndex = numberCount - maxCount;
  252. 			Arrays.fill(p, maxStartIndex, numberCount, max);
  253. 			fillSum -= maxCount * fillRange;
  254. 			Arrays.fill(p, beginIndex, maxStartIndex, minValue);
  255. 			if (fillSum != 0)
  256. 				p[maxStartIndex - 1] = minValue + fillSum;
  257. 		}
  258. 	}
  259.  
  260. 	@Override
  261. 	public int[] get() { // returns null when there is no more partition, then starts over
  262. 		if (finished) {
  263. 			startOver();
  264. 			return null;
  265. 		}
  266. 		int[] pCopy = p.clone();
  267. 		if (numberCount > 1) {
  268. 			int i = numberCount;
  269. 			int s = p[--i];
  270. 			while (i > 0) {
  271. 				int x = p[--i];
  272. 				if (x == max) {
  273. 					s += x;
  274. 					continue;
  275. 				}
  276. 				x++;
  277. 				s--;
  278. 				int minRest = sorted ? x : min;
  279. 				if (s < minRest * (numberCount - i - 1)) {
  280. 					s += x;
  281. 					continue;
  282. 				}
  283. 				p[i++]++;
  284. 				fillMinimal(i, minRest, s);
  285. 				return pCopy;
  286. 			}
  287. 		}
  288. 		finished = true;
  289. 		return pCopy;
  290. 	}
  291.  
  292. 	public static final PartitionGenerator.GeneratorFactory permutationFactory = (numberCount, min, max, sum) ->
  293. 		new SequentialEnumerator(numberCount, min, max, sum, false);
  294. 	public static final PartitionGenerator.GeneratorFactory combinationFactory = (numberCount, min, max, sum) ->
  295. 		new SequentialEnumerator(numberCount, min, max, sum, true);
  296. }
  297.  
  298. class Test {
  299. 	private final int numberCount;
  300. 	private final int min;
  301. 	private final int max;
  302. 	private final int sum;
  303. 	private final int repeatCount;
  304. 	private final BiConsumer<PartitionGenerator, Test> procedure;
  305.  
  306. 	public Test(int numberCount, int min, int max, int sum, int repeatCount,
  307. 			BiConsumer<PartitionGenerator, Test> procedure) {
  308. 		this.numberCount = numberCount;
  309. 		this.min = min;
  310. 		this.max = max;
  311. 		this.sum = sum;
  312. 		this.repeatCount = repeatCount;
  313. 		this.procedure = procedure;
  314. 	}
  315.  
  316. 	@Override
  317. 	public String toString() {
  318. 		return String.format("=== %d numbers from [%d, %d] with sum %d, %d iterations ===",
  319. 				numberCount, min, max, sum,	repeatCount);
  320. 	}
  321.  
  322. 	private static class GeneratedVector {
  323. 		final int[] v;
  324.  
  325. 		GeneratedVector(int[] vect) {
  326. 			v = vect;
  327. 		}
  328.  
  329. 		@Override
  330. 		public int hashCode() {
  331. 			return Arrays.hashCode(v);
  332. 		}
  333.  
  334. 		@Override
  335. 		public boolean equals(Object obj) {
  336. 			if (this == obj)
  337. 				return true;
  338. 			return Arrays.equals(v, ((GeneratedVector)obj).v);
  339. 		}
  340.  
  341. 		@Override
  342. 		public String toString() {
  343. 			return Arrays.toString(v);
  344. 		}
  345. 	}
  346.  
  347. 	private static final Comparator<Map.Entry<GeneratedVector, Integer>> lexicographical = (e1, e2) -> {
  348. 		int[] v1 = e1.getKey().v;
  349. 		int[] v2 = e2.getKey().v;
  350. 		int len = v1.length;
  351. 		int d = len - v2.length;
  352. 		if (d != 0)
  353. 			return d;
  354. 		for (int i = 0; i < len; i++) {
  355. 			d = v1[i] - v2[i];
  356. 			if (d != 0)
  357. 				return d;
  358. 		}
  359. 		return 0;
  360. 	};
  361.  
  362. 	private static final Comparator<Map.Entry<GeneratedVector, Integer>> byCount =
  363. 			Comparator.<Map.Entry<GeneratedVector, Integer>>comparingInt(Map.Entry::getValue)
  364. 			.thenComparing(lexicographical);
  365.  
  366. 	public static int SHOW_MISSING_LIMIT = 10;
  367.  
  368. 	private static void checkMissingPartitions(Map<GeneratedVector, Integer> map, PartitionGenerator reference) {
  369. 		int missingCount = 0;
  370. 		while (true) {
  371. 			int[] v = reference.get();
  372. 			if (v == null)
  373. 				break;
  374. 			GeneratedVector gv = new GeneratedVector(v);
  375. 			if (!map.containsKey(gv)) {
  376. 				if (missingCount == 0)
  377. 					System.out.println(" Missing:");
  378. 				if (++missingCount > SHOW_MISSING_LIMIT) {
  379. 					System.out.println("  . . .");
  380. 					break;
  381. 				}
  382. 				System.out.println(gv);
  383. 			}
  384. 		}
  385. 	}
  386.  
  387. 	public static final BiConsumer<PartitionGenerator, Test> distributionTest(boolean sortByCount) {
  388. 		return (PartitionGenerator gen, Test test) -> {
  389. 			System.out.print("\n" + getName(gen) + "\n\n");
  390. 			Map<GeneratedVector, Integer> combos = new HashMap<>();
  391. 			// There's no point of checking permus for sorted generators
  392. 			// because they are the same as combos for them
  393. 			Map<GeneratedVector, Integer> permus = gen.isSorted() ? null : new HashMap<>();
  394. 			for (int i = 0; i < test.repeatCount; i++) {
  395. 				int[] v = gen.get();
  396. 				if (v == null && gen instanceof SequentialEnumerator)
  397. 					break;
  398. 				if (permus != null) {
  399. 					permus.merge(new GeneratedVector(v), 1, Integer::sum);
  400. 					v = v.clone();
  401. 					Arrays.sort(v);
  402. 				}
  403. 				combos.merge(new GeneratedVector(v), 1, Integer::sum);
  404. 			}
  405. 			Set<Map.Entry<GeneratedVector, Integer>> sortedEntries = new TreeSet<>(
  406. 					sortByCount ? byCount : lexicographical);
  407. 			System.out.println("Combos" + (gen.isSorted() ? ":" : " (don't have to be uniform):"));
  408. 			sortedEntries.addAll(combos.entrySet());
  409. 			for (Map.Entry<GeneratedVector, Integer> e : sortedEntries)
  410. 				System.out.println(e);
  411. 			checkMissingPartitions(combos, test.getGenerator(SequentialEnumerator.combinationFactory));
  412. 			if (permus != null) {
  413. 				System.out.println("\nPermus:");
  414. 				sortedEntries.clear();
  415. 				sortedEntries.addAll(permus.entrySet());
  416. 				for (Map.Entry<GeneratedVector, Integer> e : sortedEntries)
  417. 					System.out.println(e);
  418. 				checkMissingPartitions(permus, test.getGenerator(SequentialEnumerator.permutationFactory));
  419. 			}
  420. 		};
  421. 	}
  422.  
  423. 	public static final BiConsumer<PartitionGenerator, Test> correctnessTest =
  424. 		(PartitionGenerator gen, Test test) -> {
  425. 		String genName = getName(gen);
  426. 		for (int i = 0; i < test.repeatCount; i++) {
  427. 			int[] v = gen.get();
  428. 			if (v == null && gen instanceof SequentialEnumerator)
  429. 				v = gen.get();
  430. 			if (v.length != test.numberCount)
  431. 				throw new RuntimeException(genName + ": array of wrong length");
  432. 			int s = 0;
  433. 			if (gen.isSorted()) {
  434. 				if (v[0] < test.min || v[v.length - 1] > test.max)
  435. 					throw new RuntimeException(genName + ": generated number is out of range");
  436. 				int prev = test.min;
  437. 				for (int x : v) {
  438. 					if (x < prev)
  439. 						throw new RuntimeException(genName + ": unsorted array");
  440. 					s += x;
  441. 					prev = x;
  442. 				}
  443. 			} else
  444. 				for (int x : v) {
  445. 					if (x < test.min || x > test.max)
  446. 						throw new RuntimeException(genName + ": generated number is out of range");
  447. 					s += x;
  448. 				}
  449. 			if (s != test.sum)
  450. 				throw new RuntimeException(genName + ": wrong sum");
  451. 		}
  452. 		System.out.format("%30s :   correctness test passed%n", genName);
  453. 	};
  454.  
  455. 	public static final BiConsumer<PartitionGenerator, Test> performanceTest =
  456. 		(PartitionGenerator gen, Test test) -> {
  457. 		long time = System.nanoTime();
  458. 		for (int i = 0; i < test.repeatCount; i++)
  459. 			gen.get();
  460. 		time = System.nanoTime() - time;
  461. 		System.out.format("%30s : %8.3f s %10.0f ns/test%n", getName(gen), time * 1e-9, time * 1.0 / test.repeatCount);
  462. 	};
  463.  
  464. 	public PartitionGenerator getGenerator(PartitionGenerator.GeneratorFactory factory) {
  465. 		return factory.create(numberCount, min, max, sum);
  466. 	}
  467.  
  468. 	public static String getName(PartitionGenerator gen) {
  469. 		String name = gen.getClass().getSimpleName();
  470. 		if (gen instanceof SequentialEnumerator)
  471. 			return (gen.isSorted() ? "Sorted " : "Unsorted ") + name;
  472. 		else
  473. 			return name;
  474. 	}
  475.  
  476. 	public static PartitionGenerator.GeneratorFactory[] factories = { SmithTromblePartitionGenerator.factory,
  477. 			PermutationPartitionGenerator.factory, CombinationPartitionGenerator.factory,
  478. 			SequentialEnumerator.permutationFactory, SequentialEnumerator.combinationFactory };
  479.  
  480. 	public static void main(String[] args) {
  481. 		Test[] tests = {
  482. 							new Test(3, 0, 3, 5, 3_000, distributionTest(false)),
  483. 							new Test(3, 0, 6, 12, 3_000, distributionTest(true)),
  484. 							new Test(50, -10, 20, 70, 1_000, correctnessTest),
  485. 							new Test(7, 3, 10, 42, 25_000, performanceTest),
  486. 							new Test(20, 3, 10, 120, 1_500, performanceTest)
  487. 					   };
  488. 		for (Test t : tests) {
  489. 			System.out.println(t);
  490. 			for (PartitionGenerator.GeneratorFactory factory : factories) {
  491. 				PartitionGenerator candidate = t.getGenerator(factory);
  492. 				t.procedure.accept(candidate, t);
  493. 			}
  494. 			System.out.println();
  495. 		}
  496. 	}
  497. }
  498.  
Success #stdin #stdout 3.06s 126148KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
=== 3 numbers from [0, 3] with sum 5, 3000 iterations ===

SmithTromblePartitionGenerator

Combos (don't have to be uniform):
[0, 2, 3]=1517
[1, 1, 3]=744
[1, 2, 2]=739

Permus:
[0, 2, 3]=242
[0, 3, 2]=261
[1, 1, 3]=249
[1, 2, 2]=232
[1, 3, 1]=249
[2, 0, 3]=229
[2, 1, 2]=254
[2, 2, 1]=253
[2, 3, 0]=241
[3, 0, 2]=252
[3, 1, 1]=246
[3, 2, 0]=292

PermutationPartitionGenerator

Combos (don't have to be uniform):
[0, 2, 3]=1491
[1, 1, 3]=750
[1, 2, 2]=759

Permus:
[0, 2, 3]=248
[0, 3, 2]=267
[1, 1, 3]=252
[1, 2, 2]=262
[1, 3, 1]=239
[2, 0, 3]=246
[2, 1, 2]=260
[2, 2, 1]=237
[2, 3, 0]=247
[3, 0, 2]=219
[3, 1, 1]=259
[3, 2, 0]=264

CombinationPartitionGenerator

Combos:
[0, 2, 3]=985
[1, 1, 3]=991
[1, 2, 2]=1024

Unsorted SequentialEnumerator

Combos (don't have to be uniform):
[0, 2, 3]=6
[1, 1, 3]=3
[1, 2, 2]=3

Permus:
[0, 2, 3]=1
[0, 3, 2]=1
[1, 1, 3]=1
[1, 2, 2]=1
[1, 3, 1]=1
[2, 0, 3]=1
[2, 1, 2]=1
[2, 2, 1]=1
[2, 3, 0]=1
[3, 0, 2]=1
[3, 1, 1]=1
[3, 2, 0]=1

Sorted SequentialEnumerator

Combos:
[0, 2, 3]=1
[1, 1, 3]=1
[1, 2, 2]=1

=== 3 numbers from [0, 6] with sum 12, 3000 iterations ===

SmithTromblePartitionGenerator

Combos (don't have to be uniform):
[4, 4, 4]=113
[3, 3, 6]=297
[2, 5, 5]=301
[0, 6, 6]=315
[2, 4, 6]=638
[1, 5, 6]=654
[3, 4, 5]=682

Permus:
[6, 6, 0]=82
[3, 6, 3]=84
[6, 4, 2]=88
[6, 5, 1]=89
[5, 5, 2]=93
[2, 6, 4]=98
[4, 3, 5]=98
[5, 2, 5]=98
[3, 4, 5]=101
[6, 3, 3]=104
[3, 5, 4]=105
[5, 6, 1]=107
[6, 2, 4]=108
[1, 6, 5]=109
[3, 3, 6]=109
[2, 5, 5]=110
[6, 1, 5]=110
[4, 6, 2]=111
[4, 4, 4]=113
[4, 5, 3]=113
[6, 0, 6]=114
[2, 4, 6]=116
[4, 2, 6]=117
[0, 6, 6]=119
[1, 5, 6]=119
[5, 1, 6]=120
[5, 4, 3]=130
[5, 3, 4]=135

PermutationPartitionGenerator

Combos (don't have to be uniform):
[4, 4, 4]=104
[3, 3, 6]=313
[2, 5, 5]=322
[0, 6, 6]=347
[3, 4, 5]=610
[2, 4, 6]=647
[1, 5, 6]=657

Permus:
[5, 3, 4]=90
[2, 6, 4]=93
[6, 2, 4]=93
[4, 3, 5]=95
[4, 5, 3]=99
[5, 6, 1]=99
[2, 5, 5]=100
[5, 5, 2]=100
[3, 4, 5]=102
[3, 3, 6]=103
[4, 4, 4]=104
[3, 6, 3]=105
[6, 3, 3]=105
[6, 1, 5]=106
[5, 1, 6]=109
[1, 6, 5]=110
[5, 4, 3]=110
[6, 4, 2]=110
[6, 5, 1]=111
[6, 0, 6]=113
[3, 5, 4]=114
[0, 6, 6]=115
[4, 6, 2]=115
[4, 2, 6]=117
[2, 4, 6]=119
[6, 6, 0]=119
[1, 5, 6]=122
[5, 2, 5]=122

CombinationPartitionGenerator

Combos:
[2, 5, 5]=405
[1, 5, 6]=406
[3, 4, 5]=408
[0, 6, 6]=429
[2, 4, 6]=437
[4, 4, 4]=450
[3, 3, 6]=465

Unsorted SequentialEnumerator

Combos (don't have to be uniform):
[4, 4, 4]=1
[0, 6, 6]=3
[2, 5, 5]=3
[3, 3, 6]=3
[1, 5, 6]=6
[2, 4, 6]=6
[3, 4, 5]=6

Permus:
[0, 6, 6]=1
[1, 5, 6]=1
[1, 6, 5]=1
[2, 4, 6]=1
[2, 5, 5]=1
[2, 6, 4]=1
[3, 3, 6]=1
[3, 4, 5]=1
[3, 5, 4]=1
[3, 6, 3]=1
[4, 2, 6]=1
[4, 3, 5]=1
[4, 4, 4]=1
[4, 5, 3]=1
[4, 6, 2]=1
[5, 1, 6]=1
[5, 2, 5]=1
[5, 3, 4]=1
[5, 4, 3]=1
[5, 5, 2]=1
[5, 6, 1]=1
[6, 0, 6]=1
[6, 1, 5]=1
[6, 2, 4]=1
[6, 3, 3]=1
[6, 4, 2]=1
[6, 5, 1]=1
[6, 6, 0]=1

Sorted SequentialEnumerator

Combos:
[0, 6, 6]=1
[1, 5, 6]=1
[2, 4, 6]=1
[2, 5, 5]=1
[3, 3, 6]=1
[3, 4, 5]=1
[4, 4, 4]=1

=== 50 numbers from [-10, 20] with sum 70, 1000 iterations ===
SmithTromblePartitionGenerator :   correctness test passed
 PermutationPartitionGenerator :   correctness test passed
 CombinationPartitionGenerator :   correctness test passed
 Unsorted SequentialEnumerator :   correctness test passed
   Sorted SequentialEnumerator :   correctness test passed

=== 7 numbers from [3, 10] with sum 42, 25000 iterations ===
SmithTromblePartitionGenerator :    0.016 s        636 ns/test
 PermutationPartitionGenerator :    0.006 s        228 ns/test
 CombinationPartitionGenerator :    0.005 s        216 ns/test
 Unsorted SequentialEnumerator :    0.008 s        311 ns/test
   Sorted SequentialEnumerator :    0.045 s       1812 ns/test

=== 20 numbers from [3, 10] with sum 120, 1500 iterations ===
SmithTromblePartitionGenerator :    0.056 s      37466 ns/test
 PermutationPartitionGenerator :    0.001 s        644 ns/test
 CombinationPartitionGenerator :    0.001 s        470 ns/test
 Unsorted SequentialEnumerator :    0.000 s         30 ns/test
   Sorted SequentialEnumerator :    0.000 s         45 ns/test
https://ideone.com/CNefX8
Demo code that supplements John McClane's answer to
https://stackoverflow.com/questions/61393463/
language:
Java (12.0.1)
created:
3 years 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!