Czy istnieje skuteczny sposób na wygenerowanie N losowych liczb całkowitych w zakresie, który ma określoną sumę lub średnią?

Czy istnieje skuteczny sposób na wygenerowanie losowej kombinacji N liczb całkowitych, która:

• każda liczba całkowita znajduje się w przedziale [ min, max],
• liczby całkowite mają sumę sum,
• liczby całkowite mogą występować w dowolnej kolejności (np. losowej), oraz
• kombinacja jest wybierana równomiernie ze wszystkich kombinacji, które spełniają inne wymagania?

Czy istnieje podobny algorytm dla kombinacji losowych, w którym liczby całkowite muszą występować w posortowanej kolejności według ich wartości (a nie w dowolnej kolejności)?

(Wybranie odpowiedniej kombinacji ze średnią meanto szczególny przypadek, jeśli sum = N * mean. Ten problem jest równoważny z wygenerowaniem jednolitego losowego podziału sumna N części, z których każda jest w przedziale [ min, max] i pojawia się w dowolnej kolejności lub w uporządkowanej kolejności według ich wartości, zależnie od przypadku).

Wiem, że ten problem można rozwiązać w następujący sposób dla kombinacji, które pojawiają się w losowej kolejności (EDYCJA [27 kwietnia]: Zmodyfikowany algorytm.):

1. Jeśli N * max < sumlub N * min > sum, nie ma rozwiązania.

2. Jeśli N * max == sumistnieje tylko jedno rozwiązanie, w którym wszystkie Nliczby są równe max. Jeśli N * min == sumistnieje tylko jedno rozwiązanie, w którym wszystkie Nliczby są równe min.

3. Użyj algorytmu podanego w Smith and Tromble („Sampling from the Unit Simplex”, 2004), aby wygenerować N losowych liczb całkowitych nieujemnych z sumą sum - N * min.

4. Dodaj mindo każdego numeru wygenerowanego w ten sposób.

5. Jeśli dowolna liczba jest większa niż max, przejdź do kroku 3.

Jednak ten algorytm jest wolny, jeśli maxjest znacznie mniejszy niż sum. Na przykład, zgodnie z moimi testami (z implementacją powyższego przypadku specjalnego mean), algorytm średnio odrzuca -

• około 1,6 próbek, jeśli N = 7, min = 3, max = 10, sum = 42, ale
• około 30,6 próbek, jeśli N = 20, min = 3, max = 10, sum = 120.

Czy istnieje sposób zmodyfikowania tego algorytmu, aby był skuteczny w przypadku dużych N, a jednocześnie spełniał powyższe wymagania?

EDYTOWAĆ:

Alternatywą zasugerowaną w komentarzach jest skuteczny sposób tworzenia prawidłowej kombinacji losowej (spełniającej wszystkie wymagania oprócz ostatniego):

1. Oblicz X, liczba poprawnych kombinacji możliwe biorąc pod uwagę sum, mini max.
2. Wybierz Yjednolitą losową liczbę całkowitą w [0, X).
3. Konwertuj („unrank”) Yna prawidłową kombinację.

Czy istnieje jednak wzór do obliczania liczby prawidłowych kombinacji (lub permutacji) i czy istnieje sposób na konwersję liczby całkowitej na prawidłową kombinację? [EDYCJA (28 kwietnia): To samo dla permutacji niż kombinacji].

EDYCJA (27 kwietnia):

Po przeczytaniu Devroye's Non-Uniform Random Variate Generation (1986), mogę potwierdzić, że jest to problem z generowaniem losowej partycji. Również Ćwiczenie 2 (szczególnie część E) na stronie 661 jest istotne dla tego pytania.

EDYCJA (28 kwietnia):

Jak się okazało, algorytm, który podałem, jest jednolity, gdzie liczby całkowite są podawane w kolejności losowej , w przeciwieństwie do sortowania według ich wartości . Ponieważ oba problemy są przedmiotem ogólnego zainteresowania, zmodyfikowałem to pytanie, aby uzyskać kanoniczną odpowiedź na oba problemy.

Poniższego kodu Ruby można użyć do zweryfikowania potencjalnych rozwiązań dla jednolitości (gdzie algorithm(...)jest algorytm kandydujący):

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

EDYCJA (29 kwietnia): Ponownie dodano kod Ruby bieżącej implementacji.

Poniższy przykład kodu podano w języku Ruby, ale moje pytanie jest niezależne od języka programowania:

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
}

Oto moje rozwiązanie w Javie. Jest w pełni funkcjonalny i zawiera dwa generatory: PermutationPartitionGeneratordla nieposortowanych partycji i CombinationPartitionGeneratordla posortowanych partycji. Twój generator zaimplementowano również w klasie SmithTromblePartitionGeneratordo porównania. Klasa SequentialEnumeratorwylicza wszystkie możliwe partycje (nieposortowane lub posortowane, w zależności od parametru) w kolejności sekwencyjnej. Dodałem dokładne testy (w tym przypadki testowe) dla wszystkich tych generatorów. W większości przypadków implementacja jest łatwa do wyjaśnienia. Jeśli masz jakieś pytania, odpowiem na nie za kilka dni.

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();
        }
    }
}

Możesz to wypróbować na Ideone .

Oto algorytm z PermutationPartitionGenerator Johna McClane'a, w innej odpowiedzi na tej stronie. Ma dwie fazy, mianowicie fazę konfiguracji i fazę próbkowania i generujen liczby losowe w [ min, max] z sumą sum, gdzie liczby są wymienione w kolejności losowej.

Faza instalacji: Po pierwsze, tabela rozwiązań jest budowana przy użyciu następujących wzorów ( t(y, x)gdzie yjest w [0,n ] i xjest w [0, sum - n * min]):

• t (0, j) = 1, jeżeli j == 0; 0 w przeciwnym razie
• t (i, j) = t (i-1, j) + t (i-1, j-1) + ... + t (i-1, j- (max-min))

Tutaj t (y, x) przechowuje względne prawdopodobieństwo, że suma yliczb (w odpowiednim zakresie) będzie równax . Prawdopodobieństwo to odnosi się do wszystkich t (y, x) z tym samym y.

Faza próbkowania: Tutaj generujemy próbkę nliczb. Ustaw ssię sum - n * min, a następnie dla każdej pozycji i, poczynającn - 1 i cofając się do 0:

• Zestaw v na losową liczbę całkowitą w [0, t (i + 1, s)).
• Ustaw rnamin .
• Odejmij t (i, s) od v .
• Gdy vpozostaje 0 lub więcej, odejmij t (i, s-1) od v, dodaj 1 do ri odejmij 1 ods .
• Liczba w pozycji iw próbce jest ustawiona na r.

EDYTOWAĆ:

Wygląda na to, że przy trywialnych zmianach w powyższym algorytmie możliwe jest, aby każda liczba losowa używała osobnego zakresu zamiast używać tego samego zakresu dla wszystkich:

Każda liczba losowa na pozycjach i∈ [0, n) ma minimalną wartość min (i) i maksymalną wartość max (i).

Niech adjsum= sum- Σmin (i).

Faza konfiguracji: Po pierwsze, tabela rozwiązań jest budowana przy użyciu następujących wzorów ( t(y, x)gdzie yjest w [0,n ] i xjest w [0, adjsum]):

• t (0, j) = 1, jeżeli j == 0; 0 w przeciwnym razie
• t (i, j) = t (i-1, j) + t (i-1, j-1) + ... + t (i-1, j- (max (i-1) -min (i -1)) )

Faza próbkowania jest wtedy dokładnie taka sama jak poprzednio, z wyjątkiem tego, że ustawiliśmy sna adjsum(raczej niż sum - n * min) i ustawiliśmy rna min (i) (zamiast min).

EDYTOWAĆ:

W przypadku CombinationPartitionGenerator Johna McClane'a etapy konfiguracji i próbkowania są następujące.

Faza konfiguracji: Po pierwsze, tabela rozwiązań jest budowana przy użyciu następujących wzorów ( t(z, y, x)gdzie zjest w [0, n], yjest w [0, max - min] i xjest w [0, sum - n * min]):

• t (0, j, k) = 1, jeżeli k == 0; 0 w przeciwnym razie
• t (i, 0, k) = t (i - 1, 0, k)
• t (i, j, k) = t (i, j-1, k) + t (i - 1, j, k - j)

Faza próbkowania: Tutaj generujemy próbkę nliczb. Ustaw sna sum - n * mini mrangedo max - min, a następnie dla każdej pozycji i, zaczynając od n - 1i cofając się do 0:

• Ustaw vna losową liczbę całkowitą w [0, t (i + 1, mrange, s)).
• Ustaw mrangena min ( mrange, s)
• Odejmij mrangeod s.
• Ustaw rnamin + mrange .
• Odejmowania t ( i, mrange, s) z v.
• Natomiast vpozostałości 0 lub więcej, dodanie 1 do sodjąć od 1 ri 1 z mrange, a następnie odjąć t ( i, mrange, s) z v.
• Liczba w pozycji iw próbce jest ustawiona na r.

Nie testowałem tego, więc nie jest to tak naprawdę odpowiedź, po prostu coś, co jest zbyt długie, aby zmieściło się w komentarzu. Zacznij od tablicy, która spełnia pierwsze dwa kryteria, i baw się nią, aby nadal spełniała pierwsze dwa, ale jest o wiele bardziej losowa.

Jeśli średnia jest liczbą całkowitą, początkowa tablica może wynosić [4, 4, 4, ... 4] lub może [3, 4, 5, 3, 4, 5, ... 5, 8, 0] lub coś takiego prostego. Dla średniej 4,5 spróbuj [4, 5, 4, 5, ... 4, 5].

Następnie wybierz parę liczb num1i num2, w tablicy. Prawdopodobnie pierwszą liczbę należy wybrać w kolejności, ponieważ w przypadku losowania Fisher-Yates drugą liczbę należy wybierać losowo. Biorąc pierwszy numer w kolejności, każdy numer jest wybierany co najmniej raz.

Teraz obliczyć max-num1i num2-min. Są to odległości od dwóch liczb do granic maxi min. Ustaw limitna mniejszą z dwóch odległości. Jest to maksymalna dozwolona zmiana, która nie spowoduje, że jedna lub druga liczba przekroczy dopuszczalne limity. Jeśli limitwynosi zero, pomiń tę parę.

Wybierz losową liczbę całkowitą z zakresu [1, limit]: zadzwoń change. Pomijam 0 z zakresu możliwych do odebrania, ponieważ nie ma to wpływu. Testowanie może wykazać, że można uzyskać lepszą losowość, włączając ją; Nie jestem pewny.

Teraz ustaw num1 <- num1 + changei num2 <- num2 - change. Nie wpłynie to na średnią wartość, a wszystkie elementy tablicy nadal mieszczą się w wymaganych granicach.

Musisz przeszukać całą tablicę przynajmniej raz. Testowanie powinno pokazać, czy musisz przejść przez niego więcej niż raz, aby uzyskać coś wystarczająco losowego.

ETA: dołącz pseudokod

// 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

Jak wskazuje PO, zdolność do efektywnego unrankowania jest bardzo potężna. Jeśli jesteśmy w stanie to zrobić, wygenerowanie jednolitej dystrybucji partycji można wykonać w dwóch krokach:

1. Wygeneruj jednolity rozkład liczb całkowitych, z [1, M]których Mjest całkowita liczba partycji.
2. Odznacz każdą liczbę całkowitą

Poniżej skupiamy się tylko na wygenerowaniu n- ^tej partycji, ponieważ istnieje duża ilość informacji na temat generowania jednolitego rozkładu liczb całkowitych w danym zakresie. Oto prosty C++algorytm, który powinien być łatwy do przetłumaczenia na inne języki.

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;
}

Funkcję konia roboczego pCountzapewnia:

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;
}

Ta funkcja oparta jest na doskonałej odpowiedzi na pytanie Czy istnieje skuteczny algorytm partycjonowania liczb całkowitych z ograniczoną liczbą części? przez użytkownika @ m69_snarky_and_unwelcoming. Powyższy jest niewielką modyfikacją prostego algorytmu (ten bez zapamiętywania). Można to łatwo zmodyfikować w celu włączenia zapamiętywania dla większej wydajności.

Oto demo ideone z przykładem podanym przez OP. Możemy wygenerować 100 ^th leksykograficznej partycji gdzie min = 3, max = 10, n = 7, i sum = 42.

Oto demo ideone, które generuje pierwsze i ostatnie 10 partycji tego samego przykładu.

Wyjaśnienie

wkrótce