Есть ли эффективный способ генерировать N случайных целых чисел в диапазоне, которые имеют данную сумму или среднее значение?

Существует ли эффективный способ генерирования случайной комбинации из N целых чисел, такой что

• каждое целое число находится в интервале [ min, max],
• целые числа имеют сумму sum,
• целые числа могут появляться в любом порядке (например, в случайном порядке), и
• комбинация выбирается случайным образом из всех комбинаций, которые отвечают другим требованиям?

Существует ли подобный алгоритм для случайных комбинаций, в котором целые числа должны появляться в отсортированном порядке по их значениям (а не в любом порядке)?

(Выбор подходящей комбинации со средним значением meanявляется особым случаем, если sum = N * mean. Эта проблема эквивалентна генерации равномерного случайного разбиения sumна N частей, каждая из которых находится в интервале [ min, max] и появляется в любом порядке или в отсортированном порядке по их значения, в зависимости от обстоятельств.)

Мне известно, что эта проблема может быть решена следующим образом для комбинаций, которые появляются в случайном порядке (EDIT [27 апреля]: алгоритм изменен.):

1. Если N * max < sumили N * min > sum, нет решения.

2. Если N * max == sumесть только одно решение, в котором все Nчисла равны max. Если N * min == sumесть только одно решение, в котором все Nчисла равны min.

3. Используйте алгоритм, приведенный в работах Смита и Тромбла («Выборка из простого симплекса», 2004), чтобы сгенерировать N случайных неотрицательных целых чисел с суммой sum - N * min.

4. Добавьте minк каждому числу, созданному таким образом.

5. Если любое число больше чем 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, при этом все еще удовлетворяя вышеуказанным требованиям?

РЕДАКТИРОВАТЬ:

В качестве альтернативы, предложенной в комментариях, эффективный способ создания допустимой случайной комбинации (которая удовлетворяет всем требованиям, кроме последнего):

1. Рассчитать Xколичество допустимых комбинаций возможно при sum, minи max.
2. Выберите Y, равномерное случайное число в [0, X).
3. Конвертировать («unrank») Yв правильную комбинацию.

Однако существует ли формула для расчета количества допустимых комбинаций (или перестановок), и есть ли способ преобразовать целое число в действительную комбинацию? [РЕДАКТИРОВАТЬ (28 апреля): то же самое для перестановок, а не комбинаций].

РЕДАКТИРОВАТЬ (27 апреля):

После прочтения « Неравномерного генерирования случайных переменных» Девройа (1986) я могу подтвердить, что это проблема генерации случайного разбиения. Кроме того, упражнение 2 (особенно часть E) на стр. 661 относится к этому вопросу.

РЕДАКТИРОВАТЬ (28 апреля):

Как оказалось, алгоритм, который я дал, является унифицированным, где задействованные целые числа заданы в случайном порядке , а не в отсортированном порядке по их значениям . Поскольку обе проблемы представляют общий интерес, я изменил этот вопрос, чтобы найти канонический ответ для обеих проблем.

Следующий код Ruby может быть использован для проверки потенциальных решений для однородности (где 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

РЕДАКТИРОВАТЬ (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
}

Вот мое решение на Java. Он полностью функционален и содержит два генератора: 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 .

Вот алгоритм от PermutationPartitionGenerator Джона Макклэйна, в другом ответе на этой странице. Он имеет две фазы, а именно фазу настройки и фазу выборки, и генерирует nслучайные числа в [ min, max] с суммой sum, где числа перечислены в случайном порядке.

Этап настройки: сначала строится таблица решений с использованием следующих формул ( t(y, x)где yнаходится в [0, n] и xв [0, sum - n * min]):

• t (0, j) = 1, если j == 0; 0 иначе
• t (i, j) = t (i-1, j) + t (i-1, j-1) + ... + t (i-1, j- (max-min))

Здесь t (y, x) хранит относительную вероятность того, что сумма yчисел (в соответствующем диапазоне) будет равна x. Эта вероятность относительно всех t (y, x) с одинаковыми y.

Фаза выборки: здесь мы генерируем выборку nчисел. Установите sдля sum - n * min, затем для каждой позиции i, начиная с n - 1и возвращаясь к 0:

• Установите vслучайное целое число в [0, t (i + 1, s)).
• Установите rв min.
• Вычтите 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- Σmin (i).

Этап настройки: сначала строится таблица решений с использованием следующих формул ( t(y, x)где yнаходится в [0, n] и xв [0, adjsum]):

• t (0, j) = 1, если j == 0; 0 иначе
• t (i, j) = t (i-1, j) + t (i-1, j-1) + ... + t (i-1, j- (max (i-1)) -min (i -1)) )

Фазы дискретизации затем точно так же , как и раньше, за исключением того, мы установили , sчтобы adjsum(а не sum - n * min) и множество rв мин (я) (а не min).

РЕДАКТИРОВАТЬ:

Для CombinationPartitionGenerator Джона Макклейна фазы настройки и выборки следующие.

Этап настройки: сначала строится таблица решений с использованием следующих формул ( t(z, y, x)где zнаходится в [0, n], yв [0, max - min] и xв [0, sum - n * min]):

• t (0, j, k) = 1, если k == 0; 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.
• Вычитание т ( i, mrange, s) из v.
• Пока vостается 0 или больше, добавьте 1 к s, вычесть 1 из rи 1 из mrange, а затем вычтите т ( 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в массиве. Вероятно, первое число должно быть взято по порядку, как и в случае тасования Фишера-Йейтса, второе число должно выбираться случайным образом. Принятие первого номера по порядку гарантирует, что каждый номер будет выбран хотя бы один раз.

Теперь посчитаем max-num1и num2-min. Это расстояние от двух чисел к maxи minграницам. Установите limitменьшее из двух расстояний. Это максимально допустимое изменение, которое не поставит одно или другое число за допустимые пределы. Если limitноль, то пропустите эту пару.

Выберите случайное целое число в диапазоне [1, limit]: вызовите его 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

Как указывает ОП, способность эффективно отменить ставку очень мощная. Если мы сможем это сделать, генерация равномерного распределения разделов может быть выполнена в три этапа (повторяя то, что ОП изложил в вопросе):

1. Вычислите общее количество M разделов длины N числа sum, чтобы части находились в диапазоне [ min, max].
2. Генерация равномерного распределения целых чисел из [1, M].
3. Снимите все целые числа с шага 2 в соответствующий раздел.

Ниже мы сконцентрируемся только на генерации n- ^го раздела, поскольку существует огромное количество информации о генерации равномерного распределения целых чисел в заданном диапазоне. Вот простой C++алгоритм отмены рейтинга, который должен быть легко переведен на другие языки (NB. Я еще не выяснил, как отменить выбор композиции (т.е. порядок имеет значение)).

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 - N * (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

Для того чтобы отсчитать количество разделов, мы должны продолжать применять перевод к «единичному» случаю. Это выглядит так:

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 случайных разделов. Выход ниже:

42: 3 3 6 7 7 8 8 
123: 4 4 6 6 6 7 9 
2: 3 3 3 4 9 10 10 
125: 4 4 6 6 7 7 8 
104: 4 4 4 6 6 8 10 
74: 3 4 6 7 7 7 8 
47: 3 4 4 5 6 10 10 
146: 5 5 5 5 6 7 9 
70: 3 4 6 6 6 7 10 
134: 4 5 5 6 6 7 9 
136: 4 5 5 6 7 7 8 
81: 3 5 5 5 8 8 8 
122: 4 4 6 6 6 6 10 
112: 4 4 5 5 6 8 10 
147: 5 5 5 5 6 8 8 
142: 4 6 6 6 6 7 7 
37: 3 3 6 6 6 9 9 
67: 3 4 5 6 8 8 8 
45: 3 4 4 4 8 9 10 
44: 3 4 4 4 7 10 10

Слева находится лексикографический указатель, а справа - раздел без рейтинга.

Если вы сгенерируете 0≤a≤1 случайных значений в диапазоне [l, x-1] равномерно и 1-a случайных значений в диапазоне [x, h] равномерно, ожидаемое среднее значение будет:

m = ((l+x-1)/2)*a + ((x+h)/2)*(1-a)

Так что если вы хотите конкретный m, вы можете играть с а и х.

Например, если вы установите x = m: a = (hm) / (h-l + 1).

Чтобы обеспечить близкую к равномерной вероятность для различных комбинаций, выберите a или x случайным образом из набора допустимых решений уравнения выше. (x должно быть в диапазоне [l, h] и должно быть (близко к) целому числу; N * a также должно быть (близко к) целому числу.