有没有一个有效的方法来生成n个随机整数的范围内有一个给定的总和或平均数?

4xy9mtcn  于 2021-06-30  发布在  Java
关注(0)|答案(4)|浏览(380)

有没有一种有效的方法来生成n个整数的随机组合-
每个整数都在区间内[ min , max ],
整数的和为 sum ,
整数可以以任何顺序出现(例如,随机顺序),并且
从满足其他要求的所有组合中随机均匀地选择组合?
对于整数必须按其值排序(而不是按任何顺序)的随机组合,是否有类似的算法?
(选择适当的组合,平均值为 mean 是特例,如果 sum = N * mean . 这个问题等价于生成一个均匀的随机分区 sum 分成n个部分,每个部分在间隔中[ min , max ]并按任意顺序或按其值排序(视情况而定)
我知道,对于以随机顺序出现的组合,这个问题可以通过以下方式解决(编辑[4月27日]:算法修改):
如果 N * max < sum 或者 N * min > sum ,没有解决方案。
如果 N * max == sum ,只有一个解决方案,其中 N 数字等于 max . 如果 N * min == sum ,只有一个解决方案,其中 N 数字等于 min .
使用smith和tromble中给出的算法(“从单位单纯形采样”,2004年)生成n个随机非负整数和 sum - N * min .
添加 min 以这种方式生成的每个数字。
如果任何数字大于 max ,转至步骤3。
但是,如果 max 远小于 sum . 例如,根据我的测试(带有一个实现上面涉及的特例) mean ),算法平均拒绝-
约1.6个样品,如果 N = 7, min = 3, max = 10, sum = 42 ,但是
约30.6个样品,如果 N = 20, min = 3, max = 10, sum = 120 .
有没有一种方法可以在满足上述要求的情况下,对这个算法进行修改,使其对大n有效?
编辑:
作为评论中建议的另一种选择,产生有效随机组合(满足除最后一个要求外的所有要求)的有效方法是:
计算 X ,可能给定的有效组合数 sum , min ,和 max .
选择 Y ,中的均匀随机整数 [0, X) .
转换(“取消银行”) Y 一个有效的组合。
但是,是否有一个公式来计算有效组合(或置换)的数量,是否有一种方法可以将整数转换为有效组合[编辑(4月28日):相同的排列而不是组合]。
编辑(4月27日):
在阅读了devroye的非均匀随机变量生成(1986)之后,我可以确认这是一个生成随机分区的问题。此外,第661页的练习2(特别是e部分)也与这个问题有关。
编辑(4月28日):
结果证明,我给出的算法是一致的,其中所涉及的整数是按随机顺序给出的,而不是按值排序。由于这两个问题都是大家普遍关心的问题,我修改了这个问题,以寻求这两个问题的规范答案。
下面的ruby代码可用于验证一致性的潜在解决方案(其中 algorithm(...) 是候选算法):

  1. combos={}
  2. permus={}
  3. mn=0
  4. mx=6
  5. sum=12
  6. for x in mn..mx
  7. for y in mn..mx
  8. for z in mn..mx
  9. if x+y+z==sum
  10. permus[[x,y,z]]=0
  11. end
  12. if x+y+z==sum and x<=y and y<=z
  13. combos[[x,y,z]]=0
  14. end
  15. end
  16. end
  17. end
  18. 3000.times {|x|
  19. f=algorithm(3,sum,mn,mx)
  20. combos[f.sort]+=1
  21. permus[f]+=1
  22. }
  23. p combos
  24. p permus

编辑(4月29日):重新添加了当前实现的ruby代码。
下面的代码示例是用ruby给出的,但我的问题与编程语言无关:

  1. def posintwithsum(n, total)
  2. raise if n <= 0 or total <=0
  3. ls = [0]
  4. ret = []
  5. while ls.length < n
  6. c = 1+rand(total-1)
  7. found = false
  8. for j in 1...ls.length
  9. if ls[j] == c
  10. found = true
  11. break
  12. end
  13. end
  14. if found == false;ls.push(c);end
  15. end
  16. ls.sort!
  17. ls.push(total)
  18. for i in 1...ls.length
  19. ret.push(ls[i] - ls[i - 1])
  20. end
  21. return ret
  22. end
  23. def integersWithSum(n, total)
  24. raise if n <= 0 or total <=0
  25. ret = posintwithsum(n, total + n)
  26. for i in 0...ret.length
  27. ret[i] = ret[i] - 1
  28. end
  29. return ret
  30. end
  31. # Generate 100 valid samples
  32. mn=3
  33. mx=10
  34. sum=42
  35. n=7
  36. 100.times {
  37. while true
  38. pp=integersWithSum(n,sum-n*mn).map{|x| x+mn }
  39. if !pp.find{|x| x>mx }
  40. p pp; break # Output the sample and break
  41. end
  42. end
  43. }
fiei3ece

fiei3ece1#

正如op所指出的,有效地拆借的能力非常强大。如果我们能够做到这一点,那么生成分区的统一分布可以分为三个步骤(重申op在问题中的布局):
计算长度为n的分区的总数m sum 使零件在范围内[ min , max ].
生成整数的均匀分布 [1, M] .
将步骤2中的每个整数解列到其各自的分区中。
下面,我们只关注生成第n个分区,因为在给定范围内生成整数的均匀分布有大量的信息。这里有一个简单的例子 C++ 解题算法,应该很容易翻译成其他语言(注意,我还没有弄清楚如何解题的组成情况(即顺序问题))。

  1. std::vector<int> unRank(int n, int m, int myMax, int nth) {
  2. std::vector<int> z(m, 0);
  3. int count = 0;
  4. int j = 0;
  5. for (int i = 0; i < z.size(); ++i) {
  6. int temp = pCount(n - 1, m - 1, myMax);
  7. for (int r = n - m, k = myMax - 1;
  8. (count + temp) < nth && r > 0 && k; r -= m, --k) {
  9. count += temp;
  10. n = r;
  11. myMax = k;
  12. ++j;
  13. temp = pCount(n - 1, m - 1, myMax);
  14. }
  15. --m;
  16. --n;
  17. z[i] = j;
  18. }
  19. return z;
  20. }

主力军 pCount 函数由下式给出:

  1. int pCount(int n, int m, int myMax) {
  2. if (myMax * m < n) return 0;
  3. if (myMax * m == n) return 1;
  4. if (m < 2) return m;
  5. if (n < m) return 0;
  6. if (n <= m + 1) return 1;
  7. int niter = n / m;
  8. int count = 0;
  9. for (; niter--; n -= m, --myMax) {
  10. count += pCount(n - 1, m - 1, myMax);
  11. }
  12. return count;
  13. }

这个函数是基于一个很好的答案:有没有一个有效的算法,整数分割与限制

展开查看全部
ohfgkhjo

ohfgkhjo2#

我还没有测试过这个,所以这不是一个真正的答案,只是一些尝试,这是太长了,不能纳入一个评论。从一个满足前两个条件的数组开始玩,这样它仍然满足前两个条件,但随机性要大得多。
如果均值是整数,那么初始数组可以是[4,4,4。。。4] 或者[3,4,5,3,4,5。。。5,8,0]或者类似的简单的东西。如果平均值为4.5,请尝试[4,5,4,5。。。4, 5].
接下来选一对数字, num1 以及 num2 ,在数组中。可能第一个数字应该按顺序取,就像fisher-yates洗牌一样,第二个数字应该随机选取。将第一个数字按顺序排列可以确保每个数字至少拾取一次。
现在计算 max-num1 以及 num2-min . 这是从两个数字到另一个数字的距离 max 以及 min 边界。套 limit 两个距离中的较小者。这是允许的最大变化,不会使一个或另一个数字超出允许的限制。如果 limit 如果为零,则跳过这一对。
选取[1]范围内的随机整数, limit ]:叫它 change . 我从可选取范围中省略了0,因为它没有效果。测试可能会显示,你得到更好的随机性,包括它;我不确定。
现在开始 num1 <- num1 + change 以及 num2 <- num2 - change . 这不会影响平均值,并且数组的所有元素仍在所需边界内。
您需要至少遍历整个阵列一次。测试应该显示您是否需要多次运行它以获得足够的随机性。
eta:包含伪码

  1. // Set up the array.
  2. resultAry <- new array size N
  3. for (i <- 0 to N-1)
  4. // More complex initial setup schemes are possible here.
  5. resultAry[i] <- mean
  6. rof
  7. // Munge the array entries.
  8. for (ix1 <- 0 to N-1) // ix1 steps through the array in order.
  9. // Pick second entry different from first.
  10. repeat
  11. ix2 <- random(0, N-1)
  12. until (ix2 != ix1)
  13. // Calculate size of allowed change.
  14. hiLimit <- max - resultAry[ix1]
  15. loLimit <- resultAry[ix2] - min
  16. limit <- minimum(hiLimit, loLimit)
  17. if (limit == 0)
  18. // No change possible so skip.
  19. continue loop with next ix1
  20. fi
  21. // Change the two entries keeping same mean.
  22. change <- random(1, limit) // Or (0, limit) possibly.
  23. resultAry[ix1] <- resultAry[ix1] + change
  24. resultAry[ix2] <- resultAry[ix2] - change
  25. rof
  26. // Check array has been sufficiently munged.
  27. if (resultAry not random enough)
  28. munge the array again
  29. fi
展开查看全部
flvtvl50

flvtvl503#

这是我的java解决方案。它功能齐全,包含两个发电机: PermutationPartitionGenerator 对于未排序的分区和 CombinationPartitionGenerator 对于已排序的分区。生成器也在类中实现 SmithTromblePartitionGenerator 作为比较。班级 SequentialEnumerator 按顺序枚举所有可能的分区(未排序或已排序,取决于参数)。我已经为所有这些生成器添加了全面的测试(包括您的测试用例)。实现在很大程度上是可以自我解释的。如果你有任何问题,我会在几天内回答。

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

你可以在ideone上试试这个。

展开查看全部
r7s23pms

r7s23pms4#

这是约翰·麦克莱恩的置换分区生成器的算法,在本页的另一个答案中。它有两个阶段,即设置阶段和采样阶段,并生成 n 随机数[ min , max ]与总和 sum ,其中数字以随机顺序列出。
设置阶段:首先,使用以下公式构建解决方案表( t(y, x) 哪里 y 在[0, n ]以及 x 在[0, sum - n * min ]):
如果j==0,t(0,j)=1;否则为0
t(i,j)=t(i-1,j)+t(i-1,j-1)+…+t(i-1,j-(最大-最小))
这里,t(y,x)存储 y 数字(在适当的范围内)将相等 x . 这个概率是相对于所有t(y,x)具有相同的 y .
采样阶段:这里我们生成 n 数字。套 ssum - n * min ,然后针对每个位置 i ,从 n - 1 并向后工作到0:
v 到[0,t(i+1,s)中的随机整数。
rmin .
从中减去t(i,s) v .
v 保持0或更大,从中减去t(i,s-1) v ,将1添加到 r ,并从中减去1 s .
位置上的数字 i 在示例中设置为 r .
编辑:
通过对上述算法的细微更改,可以让每个随机数使用单独的范围,而不是对所有随机数使用相同的范围:
每个位置的随机数 i ∈ [0, n )具有最小值min(i)和最大值max(i)。
adjsum = sum - σ最小值(i)。
设置阶段:首先,使用以下公式构建解决方案表( t(y, x) 哪里 y 在[0, n ]以及 x 在[0, adjsum ]):
如果j==0,t(0,j)=1;否则为0
t(i,j)=t(i-1,j)+t(i-1,j-1)+…+t(i-1,j-(最大值(i-1)-最小值(i-1)))
采样阶段与之前完全相同,只是我们设置了 sadjsum (而不是 sum - n * min )并设置 r 至min(i)(而不是 min ).
编辑:
对于john mcclane的combinationpartitiongenerator,设置和采样阶段如下。
设置阶段:首先,使用以下公式构建解决方案表( t(z, y, x) 哪里 z 在[0, n ], y 在[0, max - min ],和 x 在[0, sum - n * min ]):
如果k==0,t(0,j,k)=1;否则为0
t(i,0,k)=t(i-1,0,k)
t(i,j,k)=t(i,j-1,k)+t(i-1,j,k-j)
采样阶段:这里我们生成 n 数字。套 ssum - n * min 以及 mrangemax - min ,然后针对每个位置 i ,从 n - 1 并向后工作到0:
v 到[0,t(i+1,m范围,s)中的随机整数。
mrange 至最小值( mrange , s )
减法 mranges .
rmin + mrange .
减去t( i , mrange , s )从 v .
v 保持0或更大,将1添加到 s ,从中减去1 r 一个来自 mrange ,然后减去t( i , mrange , s )从 v .
位置上的数字 i 在示例中设置为 r .

展开查看全部

相关问题