N 정수의 무작위 조합을 생성하는 효율적인 방법이 있습니까?
- 각 정수는 [
min,max] 간격으로 - 정수는의 합이
sum, - 정수는 임의의 순서 (예 : 임의 순서)로 나타날 수 있으며
- 조합은 다른 요구 사항을 충족하는 모든 조합 중에서 무작위로 균일하게 선택됩니까?
정수가 임의의 순서가 아닌 값을 기준으로 정렬 된 순서로 표시되어야하는 무작위 조합에 대한 비슷한 알고리즘이 있습니까?
( 이 mean경우, 평균과 함께 적절한 조합을 선택하는 것은 특별한 경우 sum = N * mean입니다.이 문제는 sum간격 [ min, max] 에서 각각 N 개의 부분으로 균일 한 랜덤 파티션을 생성하는 것과 동일하며 순서에 따라 순서대로 정렬됩니다. 경우에 따라 값)
임의의 순서로 나타나는 조합에 대해 다음과 같은 방식으로이 문제를 해결할 수 있음을 알고 있습니다 (편집 [4 월 27 일 : 알고리즘 수정 됨).
-
만약
N * max < sum나N * min > sum, 해결 방법이 없습니다. -
인 경우
N * max == sum모든N숫자가 인 솔루션이 하나만max있습니다. 인 경우N * min == sum모든N숫자가 인 솔루션이 하나만min있습니다. -
Smith와 Tromble ( “Sampling from Unit Simplex”, 2004)에 제공된 알고리즘을 사용하여 sum과 함께 음수가 아닌 N 개의 정수를 생성합니다
sum - N * min. -
추가
min이 방법으로 생성 된 각 번호. -
숫자가보다 큰 경우
max3 단계로 이동하십시오.
그러나이 알고리즘 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유효한 조합으로 변환하십시오 ( “unrank”) .
그러나 유효한 조합 (또는 순열)의 수를 계산하는 공식이 있으며 정수를 유효한 조합으로 변환하는 방법이 있습니까? [편집 (4 월 28 일) : 조합이 아닌 순열에 대해 동일].
편집 (4 월 27 일) :
Devroye의 Non-Uniform Random Variate Generation (1986)을 읽은 후 이것이 랜덤 파티션을 생성하는 데 문제가 있음을 확인할 수 있습니다. 또한 661 페이지의 연습 2 (특히 E 부분)가이 질문과 관련이 있습니다.
편집 (4 월 28 일) :
그것이 내가 준 알고리즘은 값에 의해 정렬 된 순서 와 반대로 임의의 순서 로 주어진 정수가 주어진 곳에서 균일 합니다 . 두 문제 모두 일반적인 관심사이므로이 문제를 수정하여 두 문제에 대한 정식 답변을 구했습니다.
다음 루비 코드를 사용하여 균일성에 대한 잠재적 인 솔루션을 확인할 수 있습니다 ( algorithm(...)후보 알고리즘은 어디에 있습니까 ).
combos={}
permus={}
mn=0
mx=6
sum=12
for x in mn..mx
for y in mn..mx
for z in mn..mx
if x+y+z==sum
permus[[x,y,z]]=0
end
if x+y+z==sum and x<=y and y<=z
combos[[x,y,z]]=0
end
end
end
end
3000.times {|x|
f=algorithm(3,sum,mn,mx)
combos[f.sort]+=1
permus[f]+=1
}
p combos
p permus편집 (4 월 29 일) : 현재 구현 된 Ruby 코드를 다시 추가했습니다.
다음 코드 예제는 Ruby로 제공되지만 제 질문은 프로그래밍 언어와 무관합니다.
def posintwithsum(n, total)
raise if n <= 0 or total <=0
ls = [0]
ret = []
while ls.length < n
c = 1+rand(total-1)
found = false
for j in 1...ls.length
if ls[j] == c
found = true
break
end
end
if found == false;ls.push(c);end
end
ls.sort!
ls.push(total)
for i in 1...ls.length
ret.push(ls[i] - ls[i - 1])
end
return ret
end
def integersWithSum(n, total)
raise if n <= 0 or total <=0
ret = posintwithsum(n, total + n)
for i in 0...ret.length
ret[i] = ret[i] - 1
end
return ret
end
# Generate 100 valid samples
mn=3
mx=10
sum=42
n=7
100.times {
while true
pp=integersWithSum(n,sum-n*mn).map{|x| x+mn }
if !pp.find{|x| x>mx }
p pp; break # Output the sample and break
end
end
}
답변
여기 내 자바 솔루션이 있습니다. 그것은 완벽하게 작동하며 PermutationPartitionGenerator분류되지 않은 파티션과 CombinationPartitionGenerator정렬 된 파티션을 위한 두 개의 생성기를 포함 합니다. 또한 발전기는 SmithTromblePartitionGenerator비교 를 위해 클래스에서 구현되었습니다 . 이 클래스는 SequentialEnumerator가능한 모든 파티션 (매개 변수에 따라 정렬되지 않은 또는 정렬 된)을 순차적으로 열거합니다. 이 모든 발전기에 대해 철저한 테스트 (테스트 케이스 포함)를 추가했습니다. 구현은 대부분 자체 설명 가능합니다. 궁금한 점이 있으면 며칠 후에 답변 해 드리겠습니다.
import java.util.Random;
import java.util.function.Supplier;
public abstract class PartitionGenerator implements Supplier<int[]>{
public static final Random rand = new Random();
protected final int numberCount;
protected final int min;
protected final int range;
protected final int sum; // shifted sum
protected final boolean sorted;
protected PartitionGenerator(int numberCount, int min, int max, int sum, boolean sorted) {
if (numberCount <= 0)
throw new IllegalArgumentException("Number count should be positive");
this.numberCount = numberCount;
this.min = min;
range = max - min;
if (range < 0)
throw new IllegalArgumentException("min > max");
sum -= numberCount * min;
if (sum < 0)
throw new IllegalArgumentException("Sum is too small");
if (numberCount * range < sum)
throw new IllegalArgumentException("Sum is too large");
this.sum = sum;
this.sorted = sorted;
}
// Whether this generator returns sorted arrays (i.e. combinations)
public final boolean isSorted() {
return sorted;
}
public interface GeneratorFactory {
PartitionGenerator create(int numberCount, int min, int max, int sum);
}
}
import java.math.BigInteger;
// Permutations with repetition (i.e. unsorted vectors) with given sum
public class PermutationPartitionGenerator extends PartitionGenerator {
private final double[][] distributionTable;
public PermutationPartitionGenerator(int numberCount, int min, int max, int sum) {
super(numberCount, min, max, sum, false);
distributionTable = calculateSolutionCountTable();
}
private double[][] calculateSolutionCountTable() {
double[][] table = new double[numberCount + 1][sum + 1];
BigInteger[] a = new BigInteger[sum + 1];
BigInteger[] b = new BigInteger[sum + 1];
for (int i = 1; i <= sum; i++)
a[i] = BigInteger.ZERO;
a[0] = BigInteger.ONE;
table[0][0] = 1.0;
for (int n = 1; n <= numberCount; n++) {
double[] t = table[n];
for (int s = 0; s <= sum; s++) {
BigInteger z = BigInteger.ZERO;
for (int i = Math.max(0, s - range); i <= s; i++)
z = z.add(a[i]);
b[s] = z;
t[s] = z.doubleValue();
}
// swap a and b
BigInteger[] c = b;
b = a;
a = c;
}
return table;
}
@Override
public int[] get() {
int[] p = new int[numberCount];
int s = sum; // current sum
for (int i = numberCount - 1; i >= 0; i--) {
double t = rand.nextDouble() * distributionTable[i + 1][s];
double[] tableRow = distributionTable[i];
int oldSum = s;
// lowerBound is introduced only for safety, it shouldn't be crossed
int lowerBound = s - range;
if (lowerBound < 0)
lowerBound = 0;
s++;
do
t -= tableRow[--s];
// s can be equal to lowerBound here with t > 0 only due to imprecise subtraction
while (t > 0 && s > lowerBound);
p[i] = min + (oldSum - s);
}
assert s == 0;
return p;
}
public static final GeneratorFactory factory = (numberCount, min, max,sum) ->
new PermutationPartitionGenerator(numberCount, min, max, sum);
}
import java.math.BigInteger;
// Combinations with repetition (i.e. sorted vectors) with given sum
public class CombinationPartitionGenerator extends PartitionGenerator {
private final double[][][] distributionTable;
public CombinationPartitionGenerator(int numberCount, int min, int max, int sum) {
super(numberCount, min, max, sum, true);
distributionTable = calculateSolutionCountTable();
}
private double[][][] calculateSolutionCountTable() {
double[][][] table = new double[numberCount + 1][range + 1][sum + 1];
BigInteger[][] a = new BigInteger[range + 1][sum + 1];
BigInteger[][] b = new BigInteger[range + 1][sum + 1];
double[][] t = table[0];
for (int m = 0; m <= range; m++) {
a[m][0] = BigInteger.ONE;
t[m][0] = 1.0;
for (int s = 1; s <= sum; s++) {
a[m][s] = BigInteger.ZERO;
t[m][s] = 0.0;
}
}
for (int n = 1; n <= numberCount; n++) {
t = table[n];
for (int m = 0; m <= range; m++)
for (int s = 0; s <= sum; s++) {
BigInteger z;
if (m == 0)
z = a[0][s];
else {
z = b[m - 1][s];
if (m <= s)
z = z.add(a[m][s - m]);
}
b[m][s] = z;
t[m][s] = z.doubleValue();
}
// swap a and b
BigInteger[][] c = b;
b = a;
a = c;
}
return table;
}
@Override
public int[] get() {
int[] p = new int[numberCount];
int m = range; // current max
int s = sum; // current sum
for (int i = numberCount - 1; i >= 0; i--) {
double t = rand.nextDouble() * distributionTable[i + 1][m][s];
double[][] tableCut = distributionTable[i];
if (s < m)
m = s;
s -= m;
while (true) {
t -= tableCut[m][s];
// m can be 0 here with t > 0 only due to imprecise subtraction
if (t <= 0 || m == 0)
break;
m--;
s++;
}
p[i] = min + m;
}
assert s == 0;
return p;
}
public static final GeneratorFactory factory = (numberCount, min, max, sum) ->
new CombinationPartitionGenerator(numberCount, min, max, sum);
}
import java.util.*;
public class SmithTromblePartitionGenerator extends PartitionGenerator {
public SmithTromblePartitionGenerator(int numberCount, int min, int max, int sum) {
super(numberCount, min, max, sum, false);
}
@Override
public int[] get() {
List<Integer> ls = new ArrayList<>(numberCount + 1);
int[] ret = new int[numberCount];
int increasedSum = sum + numberCount;
while (true) {
ls.add(0);
while (ls.size() < numberCount) {
int c = 1 + rand.nextInt(increasedSum - 1);
if (!ls.contains(c))
ls.add(c);
}
Collections.sort(ls);
ls.add(increasedSum);
boolean good = true;
for (int i = 0; i < numberCount; i++) {
int x = ls.get(i + 1) - ls.get(i) - 1;
if (x > range) {
good = false;
break;
}
ret[i] = x;
}
if (good) {
for (int i = 0; i < numberCount; i++)
ret[i] += min;
return ret;
}
ls.clear();
}
}
public static final GeneratorFactory factory = (numberCount, min, max, sum) ->
new SmithTromblePartitionGenerator(numberCount, min, max, sum);
}
import java.util.Arrays;
// Enumerates all partitions with given parameters
public class SequentialEnumerator extends PartitionGenerator {
private final int max;
private final int[] p;
private boolean finished;
public SequentialEnumerator(int numberCount, int min, int max, int sum, boolean sorted) {
super(numberCount, min, max, sum, sorted);
this.max = max;
p = new int[numberCount];
startOver();
}
private void startOver() {
finished = false;
int unshiftedSum = sum + numberCount * min;
fillMinimal(0, Math.max(min, unshiftedSum - (numberCount - 1) * max), unshiftedSum);
}
private void fillMinimal(int beginIndex, int minValue, int fillSum) {
int fillRange = max - minValue;
if (fillRange == 0)
Arrays.fill(p, beginIndex, numberCount, max);
else {
int fillCount = numberCount - beginIndex;
fillSum -= fillCount * minValue;
int maxCount = fillSum / fillRange;
int maxStartIndex = numberCount - maxCount;
Arrays.fill(p, maxStartIndex, numberCount, max);
fillSum -= maxCount * fillRange;
Arrays.fill(p, beginIndex, maxStartIndex, minValue);
if (fillSum != 0)
p[maxStartIndex - 1] = minValue + fillSum;
}
}
@Override
public int[] get() { // returns null when there is no more partition, then starts over
if (finished) {
startOver();
return null;
}
int[] pCopy = p.clone();
if (numberCount > 1) {
int i = numberCount;
int s = p[--i];
while (i > 0) {
int x = p[--i];
if (x == max) {
s += x;
continue;
}
x++;
s--;
int minRest = sorted ? x : min;
if (s < minRest * (numberCount - i - 1)) {
s += x;
continue;
}
p[i++]++;
fillMinimal(i, minRest, s);
return pCopy;
}
}
finished = true;
return pCopy;
}
public static final GeneratorFactory permutationFactory = (numberCount, min, max, sum) ->
new SequentialEnumerator(numberCount, min, max, sum, false);
public static final GeneratorFactory combinationFactory = (numberCount, min, max, sum) ->
new SequentialEnumerator(numberCount, min, max, sum, true);
}
import java.util.*;
import java.util.function.BiConsumer;
import PartitionGenerator.GeneratorFactory;
public class Test {
private final int numberCount;
private final int min;
private final int max;
private final int sum;
private final int repeatCount;
private final BiConsumer<PartitionGenerator, Test> procedure;
public Test(int numberCount, int min, int max, int sum, int repeatCount,
BiConsumer<PartitionGenerator, Test> procedure) {
this.numberCount = numberCount;
this.min = min;
this.max = max;
this.sum = sum;
this.repeatCount = repeatCount;
this.procedure = procedure;
}
@Override
public String toString() {
return String.format("=== %d numbers from [%d, %d] with sum %d, %d iterations ===",
numberCount, min, max, sum, repeatCount);
}
private static class GeneratedVector {
final int[] v;
GeneratedVector(int[] vect) {
v = vect;
}
@Override
public int hashCode() {
return Arrays.hashCode(v);
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
return Arrays.equals(v, ((GeneratedVector)obj).v);
}
@Override
public String toString() {
return Arrays.toString(v);
}
}
private static final Comparator<Map.Entry<GeneratedVector, Integer>> lexicographical = (e1, e2) -> {
int[] v1 = e1.getKey().v;
int[] v2 = e2.getKey().v;
int len = v1.length;
int d = len - v2.length;
if (d != 0)
return d;
for (int i = 0; i < len; i++) {
d = v1[i] - v2[i];
if (d != 0)
return d;
}
return 0;
};
private static final Comparator<Map.Entry<GeneratedVector, Integer>> byCount =
Comparator.<Map.Entry<GeneratedVector, Integer>>comparingInt(Map.Entry::getValue)
.thenComparing(lexicographical);
public static int SHOW_MISSING_LIMIT = 10;
private static void checkMissingPartitions(Map<GeneratedVector, Integer> map, PartitionGenerator reference) {
int missingCount = 0;
while (true) {
int[] v = reference.get();
if (v == null)
break;
GeneratedVector gv = new GeneratedVector(v);
if (!map.containsKey(gv)) {
if (missingCount == 0)
System.out.println(" Missing:");
if (++missingCount > SHOW_MISSING_LIMIT) {
System.out.println(" . . .");
break;
}
System.out.println(gv);
}
}
}
public static final BiConsumer<PartitionGenerator, Test> distributionTest(boolean sortByCount) {
return (PartitionGenerator gen, Test test) -> {
System.out.print("\n" + getName(gen) + "\n\n");
Map<GeneratedVector, Integer> combos = new HashMap<>();
// There's no point of checking permus for sorted generators
// because they are the same as combos for them
Map<GeneratedVector, Integer> permus = gen.isSorted() ? null : new HashMap<>();
for (int i = 0; i < test.repeatCount; i++) {
int[] v = gen.get();
if (v == null && gen instanceof SequentialEnumerator)
break;
if (permus != null) {
permus.merge(new GeneratedVector(v), 1, Integer::sum);
v = v.clone();
Arrays.sort(v);
}
combos.merge(new GeneratedVector(v), 1, Integer::sum);
}
Set<Map.Entry<GeneratedVector, Integer>> sortedEntries = new TreeSet<>(
sortByCount ? byCount : lexicographical);
System.out.println("Combos" + (gen.isSorted() ? ":" : " (don't have to be uniform):"));
sortedEntries.addAll(combos.entrySet());
for (Map.Entry<GeneratedVector, Integer> e : sortedEntries)
System.out.println(e);
checkMissingPartitions(combos, test.getGenerator(SequentialEnumerator.combinationFactory));
if (permus != null) {
System.out.println("\nPermus:");
sortedEntries.clear();
sortedEntries.addAll(permus.entrySet());
for (Map.Entry<GeneratedVector, Integer> e : sortedEntries)
System.out.println(e);
checkMissingPartitions(permus, test.getGenerator(SequentialEnumerator.permutationFactory));
}
};
}
public static final BiConsumer<PartitionGenerator, Test> correctnessTest =
(PartitionGenerator gen, Test test) -> {
String genName = getName(gen);
for (int i = 0; i < test.repeatCount; i++) {
int[] v = gen.get();
if (v == null && gen instanceof SequentialEnumerator)
v = gen.get();
if (v.length != test.numberCount)
throw new RuntimeException(genName + ": array of wrong length");
int s = 0;
if (gen.isSorted()) {
if (v[0] < test.min || v[v.length - 1] > test.max)
throw new RuntimeException(genName + ": generated number is out of range");
int prev = test.min;
for (int x : v) {
if (x < prev)
throw new RuntimeException(genName + ": unsorted array");
s += x;
prev = x;
}
} else
for (int x : v) {
if (x < test.min || x > test.max)
throw new RuntimeException(genName + ": generated number is out of range");
s += x;
}
if (s != test.sum)
throw new RuntimeException(genName + ": wrong sum");
}
System.out.format("%30s : correctness test passed%n", genName);
};
public static final BiConsumer<PartitionGenerator, Test> performanceTest =
(PartitionGenerator gen, Test test) -> {
long time = System.nanoTime();
for (int i = 0; i < test.repeatCount; i++)
gen.get();
time = System.nanoTime() - time;
System.out.format("%30s : %8.3f s %10.0f ns/test%n", getName(gen), time * 1e-9, time * 1.0 / test.repeatCount);
};
public PartitionGenerator getGenerator(GeneratorFactory factory) {
return factory.create(numberCount, min, max, sum);
}
public static String getName(PartitionGenerator gen) {
String name = gen.getClass().getSimpleName();
if (gen instanceof SequentialEnumerator)
return (gen.isSorted() ? "Sorted " : "Unsorted ") + name;
else
return name;
}
public static GeneratorFactory[] factories = { SmithTromblePartitionGenerator.factory,
PermutationPartitionGenerator.factory, CombinationPartitionGenerator.factory,
SequentialEnumerator.permutationFactory, SequentialEnumerator.combinationFactory };
public static void main(String[] args) {
Test[] tests = {
new Test(3, 0, 3, 5, 3_000, distributionTest(false)),
new Test(3, 0, 6, 12, 3_000, distributionTest(true)),
new Test(50, -10, 20, 70, 2_000, correctnessTest),
new Test(7, 3, 10, 42, 1_000_000, performanceTest),
new Test(20, 3, 10, 120, 100_000, performanceTest)
};
for (Test t : tests) {
System.out.println(t);
for (GeneratorFactory factory : factories) {
PartitionGenerator candidate = t.getGenerator(factory);
t.procedure.accept(candidate, t);
}
System.out.println();
}
}
}Ideone에서 이것을 시도 할 수 있습니다 .
답변
다음은 John McClane ‘s PermutationPartitionGenerator의 알고리즘이며이 페이지의 다른 답변입니다. 설정 단계와 샘플링 단계의 두 단계로 구성 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숫자 샘플을 생성 합니다. 설정 s에 sum - n * min각 위치에 대해 다음 i부터 시작, n - 10으로 거꾸로 작동 :
v[0, t (i + 1, s))에서 임의의 정수로 설정하십시오 .- 설정
r에min. - 에서 t (i, s)를 뺍니다
v. - 반면
v나머지 0보다 빼기 t (나는, S-1)에서v, 1을 추가r하고, 1을 뺀다s. i샘플의 위치 번호 는로 설정됩니다r.
편집하다:
위의 알고리즘을 사소하게 변경하면 각 임의의 숫자가 모두 동일한 범위를 사용하는 대신 별도의 범위를 사용하는 것이 가능합니다.
위치 i∈ [0, n)의 각 난수 는 최소값 min (i) 및 최대 값 max (i)를 갖습니다.
하자 adjsum= sum-Σmin (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)) )
우리는 것을 제외 샘플링 위상은, 그 이전과 완전히 동일하다 s에 adjsum(보다 sum - n * min)과 세트 r분이다 (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숫자 샘플을 생성 합니다. 설정 s에 sum - n * min와 mrange에 max - min각 위치에 대한 다음, i로 시작 n - 1하고 0으로 거꾸로 작동 :
v[0, t (i + 1, mrange, s))에서 임의의 정수로 설정하십시오 .- 설정
mrange분에 (mrange,s) - 빼기
mrange에서s. - 설정
r에min + mrange. - 빼기 t (
i,mrange,s)로부터v. - 하지만
v남아 0 이상은 1을 추가s, 1 빼기r에서 1을mrange빼기 t (다음,i,mrange,s에서)v. i샘플의 위치 번호 는로 설정됩니다r.
답변
나는 이것을 테스트하지 않았으므로 실제로 대답이 아니며, 너무 길어서 주석에 맞지 않는 것입니다. 처음 두 가지 기준을 충족하는 배열로 시작하여 처음 두 가지를 충족 시키지만 훨씬 더 무작위입니다.
평균이 정수이면 초기 배열은 [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] 범위에서 임의의 정수를 선택하십시오 : call it change. 효과가 없으므로 선택 가능한 범위에서 0을 생략합니다. 테스트 결과 포함하면 더 나은 임의성을 얻을 수 있습니다. 잘 모르겠습니다.
이제 설정 num1 <- num1 + change하고 num2 <- num2 - change. 이는 평균값에 영향을 미치지 않으며 배열의 모든 요소가 여전히 필요한 경계 내에 있습니다.
전체 어레이를 한 번 이상 실행해야합니다. 충분히 무작위로 무언가를 얻으려면 테스트를 두 번 이상 실행 해야하는지 테스트해야합니다.
ETA : 의사 코드 포함
// Set up the array.
resultAry <- new array size N
for (i <- 0 to N-1)
// More complex initial setup schemes are possible here.
resultAry[i] <- mean
rof
// Munge the array entries.
for (ix1 <- 0 to N-1) // ix1 steps through the array in order.
// Pick second entry different from first.
repeat
ix2 <- random(0, N-1)
until (ix2 != ix1)
// Calculate size of allowed change.
hiLimit <- max - resultAry[ix1]
loLimit <- resultAry[ix2] - min
limit <- minimum(hiLimit, loLimit)
if (limit == 0)
// No change possible so skip.
continue loop with next ix1
fi
// Change the two entries keeping same mean.
change <- random(1, limit) // Or (0, limit) possibly.
resultAry[ix1] <- resultAry[ix1] + change
resultAry[ix2] <- resultAry[ix2] - change
rof
// Check array has been sufficiently munged.
if (resultAry not random enough)
munge the array again
fi
답변
OP가 지적했듯이 효율적으로 순위를 해제하는 기능은 매우 강력합니다. 우리가 그렇게 할 수 있다면, 파티션의 균일 한 분포 생성은 세 단계로 수행 될 수 있습니다 (문제에서 OP가 제시 한 것을 레스트) :
- 파트가 [ , ] 범위 에 있도록 숫자 길이 N 의 파티션의 총 수 M을 계산하십시오 .
summinmax - 에서 균일 한 분포의 정수를 생성합니다
[1, M]. - 2 단계의 각 정수를 해당 파티션으로 랭킹 해제하십시오.
아래에서는 주어진 범위에서 정수의 균일 한 분포를 생성하는 데 대한 많은 양의 정보가 있으므로 n 번째 파티션 생성에만 중점을 둡니다 . 다음은 C++다른 언어로 쉽게 번역 할 수 있는 간단한 순위 지정 알고리즘입니다.
std::vector<int> unRank(int n, int m, int myMax, int nth) {
std::vector<int> z(m, 0);
int count = 0;
int j = 0;
for (int i = 0; i < z.size(); ++i) {
int temp = pCount(n - 1, m - 1, myMax);
for (int r = n - m, k = myMax - 1;
(count + temp) < nth && r > 0 && k; r -= m, --k) {
count += temp;
n = r;
myMax = k;
++j;
temp = pCount(n - 1, m - 1, myMax);
}
--m;
--n;
z[i] = j;
}
return z;
}
주요 pCount기능은 다음과 같습니다.
int pCount(int n, int m, int myMax) {
if (myMax * m < n) return 0;
if (myMax * m == n) return 1;
if (m < 2) return m;
if (n < m) return 0;
if (n <= m + 1) return 1;
int niter = n / m;
int count = 0;
for (; niter--; n -= m, --myMax) {
count += pCount(n - 1, m - 1, myMax);
}
return count;
}
이 기능은 제한된 수의 부품으로 정수 파티셔닝을위한 효율적인 알고리즘이 있습니까? 사용자 @ m69_snarky_and_unwelcoming. 위에 주어진 것은 간단한 알고리즘 (메모 화가없는 것)을 약간 수정 한 것입니다. 효율성을 높이기 위해 메모를 통합하도록 쉽게 수정할 수 있습니다. 우리는 지금 이것을 끄고 순위없는 부분에 집중할 것입니다.
설명 unRank
먼저 길이가 N 인 파티션에서 일대일로 매핑 sum하여 부분이 [ min,max ] 길이의 제한 파티션 N 개수 sum - m * (min - 1)의 부품 [ 1, max - (min - 1)].
작은 예로서, 50길이가 긴 파티션을 고려 4하여 min = 10및 max = 15. 이것은 최대 부분이 같은 50 - 4 * (10 - 1) = 14길이 의 제한된 파티션과 동일한 구조를 4갖습니다 15 - (10 - 1) = 6.
10 10 15 15 --->> 1 1 6 6
10 11 14 15 --->> 1 2 5 6
10 12 13 15 --->> 1 3 4 6
10 12 14 14 --->> 1 3 5 5
10 13 13 14 --->> 1 4 4 5
11 11 13 15 --->> 2 2 4 6
11 11 14 14 --->> 2 2 5 5
11 12 12 15 --->> 2 3 3 6
11 12 13 14 --->> 2 3 4 5
11 13 13 13 --->> 2 4 4 4
12 12 12 14 --->> 3 3 3 5
12 12 13 13 --->> 3 3 4 4
이를 염두에두고 쉽게 계산할 수 있도록 1a 단계를 추가하여 문제를 “단위”사례로 변환 할 수 있습니다.
이제 우리는 단순히 계산 문제가 있습니다. @ m69가 훌륭하게 표시되므로 문제를 작은 문제로 나눠서 파티션 수를 쉽게 계산할 수 있습니다. @ m69가 제공하는 함수는 90 %의 방법을 제공합니다. 우리는 제한이 있다는 추가 제한으로 무엇을 해야하는지 파악해야합니다. 이것이 우리가 얻는 곳입니다.
int pCount(int n, int m, int myMax) {
if (myMax * m < n) return 0;
if (myMax * m == n) return 1;
우리는 또한 myMax움직일수록 감소 할 것이라는 점을 명심해야합니다 . 우리가 6을 보면 이것은 의미가 있습니다위 번째 파티션을 맞습니다 .
2 2 4 6
여기서부터 파티션 수를 계산하려면 “unit”케이스에 번역을 계속 적용해야합니다. 이것은 다음과 같습니다
1 1 3 5
이전 단계에서 최대 값이 6 만 이제 최대 값 만 고려합니다 5.
이를 염두에두고 파티션 순위를 지정하는 것은 표준 순열 또는 조합의 순위를 지정하는 것과 다르지 않습니다. 주어진 섹션에서 파티션 수를 계산할 수 있어야합니다. 예를 들어, 10위에서 시작하는 파티션 수 10를 세려면 첫 번째 열에서를 제거하기 만하면됩니다.
10 10 15 15
10 11 14 15
10 12 13 15
10 12 14 14
10 13 13 14
10 15 15
11 14 15
12 13 15
12 14 14
13 13 14
단위 케이스로 번역 :
1 6 6
2 5 6
3 4 6
3 5 5
4 4 5
그리고 전화 pCount:
pCount(13, 3, 6) = 5
순위를 정할 임의의 정수가 주어지면 인덱스 벡터를 채울 때까지 위와 같이 더 작은 섹션과 더 작은 섹션의 파티션 수를 계속 계산합니다.
예
을 감안할 때 min = 3, max = 10, n = 7,와 sum = 42, 여기입니다 ideone의 20 개 임의의 파티션을 생성 데모.
답변
