天道酬勤,学无止境

从一个原始整数列表生成混洗整数列表的算法(Algorithm for generating lists of shuffled Integers from one original list of Integers)

问题

拥有x唯一Integers的 ArrayList ,我需要在z大小的y ArrayLists 之间随机分配它们。 请记住:

  • xyz是变量值。
  • 数字不能在结果数组上重复。
  • 结果列表不能包含相同的数字! (订购它们它们必须不同)
  • 如果计算结果数组中的出现次数,则必须尽可能地使用原始数组的每个数字与其他数字相同的次数。
  • 原始数组的所有数字都必须使用,不能不使用。
  • 如果可能,必须在 Java 7 中工作。 不是 100% 强制性的,但...
  • 产生的组合将用于类似于彩票的东西,因此它们不能太连续并且必须非常随机。 它们也将按从最小值到最大值排序。
  • 最初我尝试生成所有可能的组合,目的是获得所需的数量,但这是不可行的,因为如果您选择高值,例如 40 个数字组合 11 个,则有数百万个,并且 CPU 会卡住计算很长时间,所以我尝试开发一种更简单的算法而不计算所有组合(我在下面发布代码)。

一个示例是这样的,当您有一个由 8 个元素组成的数组的原点并且您想要输出 3 个大小为 6 的数组时:

原始数组列表:[1、2、3、4、5、6、7、8]

结果输出:[7, 5, 3, 6, 4, 8], [7, 5, 1, 8, 2, 3], [8, 1, 2, 3, 4, 6]

我开发了一种算法,在评论中进行了解释。 首先,我创建了一个包含总位置数的数组,并计算每个数字必须重复多少次才能填充输出数组。 然后我用重复必要次数的每个数字填充数组,如果数组placesByNumber (因为当我除以得到placesByNumber我四舍五入为整数)我用原始数字集中的随机数填充它. 之后,我对数字进行了洗牌,最后我填充了结果数组,记住我不能在每个结果数组中重复数字。

问题来了,有时,我会遇到最后一个数组没有完全填充的情况,因为洗牌的numbersGroup变量的最后一个数字包含在最后一个数组中。

这是一个失败的例子:

原始数组列表:[1、2、3、4、5、6、7、8]

用于填充结果数组的随机数字组:

[8, 2, 4, 4, 5, 7, 2, 3, 8, 2, 1, 5, 7, 1, 6, 3, 6, 1]

结果数组:(第三个没有 6 个元素,因为其中包含 6 和 1)

[[8, 2, 4, 5, 7, 3], [4, 2, 8, 1, 5, 7], [2, 1, 6, 3]]

我发现了一些非常难看的方法来解决它,但效率很低,我正在努力寻找一种更好、更有效的算法来实现这一点。

这是我的源代码:

public static List<List<Integer>> getOptimizedCombinations(List<Integer> numbers, int numbersPerCombination, int desiredCombinations){
    List<List<Integer>> result = new ArrayList<>();
    
    //calculate total places and how many places correspond to each number.
    int totalPlaces = numbersPerCombination * desiredCombinations;
    int placesByNumber = totalPlaces / numbers.size();
    
    //instantiating array with the total number of places
    Integer[] numbersGroup = new Integer[totalPlaces];
    
    //filling the array with the numbers, now we know how many times a number must be inside the array, 
    //so we put the numbers. First we do it in order, later we will shuffle the array.
    int pos = 0;
    for (int n : numbers) {
        for (int i=0; i<placesByNumber; i++) {
            numbersGroup[pos] = n;
            pos++;
        }
    }
    
    //if there are places for fill, we fill it with random numbers. This can be possible because when we divide the total places between the 
    //numbers size, it can give a decimal as a result, and we round it to lower binary number without decimals, so it is possible to
    //have non filled places.       
    if (pos<totalPlaces) {
        while(pos<totalPlaces) {                
            numbersGroup[pos] = numbers.get(getRandom(0, numbers.size()));
            pos++;              
        }
    }       
    
    shuffleArray(numbersGroup);
    
    //we instantiate the arraylists
    for (int i=0; i<desiredCombinations; i++) {
        result.add(new ArrayList<Integer>());
    }
                    
    //filling the arraylists with the suffled numbers
    for (int i=0; i<numbersGroup.length; i++) {
        for (int j=0; j<result.size(); j++) {
            //if the combination doesn't have the number and the combination is not full, we add the number
            if (!result.get(j).contains(numbersGroup[i]) && result.get(j).size()<numbersPerCombination) {
                result.get(j).add(numbersGroup[i]);
                break;
            }
        }
    }
    
    return result;
}

static void shuffleArray(Integer[] ar){
    Random rnd = new Random();
    for (int i = ar.length - 1; i > 0; i--)
    {
        int index = rnd.nextInt(i + 1);
        // Simple swap
        int a = ar[index];
        ar[index] = ar[i];
        ar[i] = a;
    }
}

public static int getRandom(int min, int max) {
    return (int)(Math.random() * max + min);
}

就是这样称呼的:

    ArrayList<Integer> numbers = new ArrayList<Integer>() {{ 
        add(1); 
        add(2);
        add(3); 
        add(4); 
        add(5); 
        add(6); 
        add(7);
        add(8);
    }};
    getOptimizedCombinations(numbers, 6, 3);
回答1

您可以使用Stream s 将洗牌列表限制为z元素:

List<Integer> numbers = Arrays.asList(1,2,3,4,5,6,7,8);

List<List<Integer>> result = new LinkedList<>();
for(int i = 0; i < y; i++) {
  Collections.shuffle(numbers);
  List<Integer> list = numbers.stream().limit(z).collect(Collectors.toList());
  result.add(list);
}

System.out.println(result);

也许它可以以更优雅的方式完成,但输出应该是这样的:

[[2, 8, 7, 3, 4, 6], [4, 3, 6, 5, 2, 8], [5, 2, 4, 1, 6, 8]]
回答2

理念

为了完成这项工作,我们需要

  • z < x (每个新列表的长度 < 输入列表的长度),否则我们无法填充没有重复的新列表。
  • y·z (列表数·列表长度)必须是x的倍数,否则某些数字必须比其他数字出现得更频繁。

这个想法是

  1. 随机播放输入列表。
  2. 重复输入列表,最终得到y·z数字。 这可以在不实际重复列表的情况下完成。 诀窍是使用模%运算符。
  3. 将重复的输入列表均匀地拆分为y个长度为z列表。
  4. 随机播放每个新列表。

输入

1 2 3 4 5 6 7 8

随机播放

3 5 8 6 7 2 4 1

重复

3 5 8 6 7 2 4 1 3 5 8 6 7 2 4 1 3 5 8 6 7 2 4 1

分裂

3 5 8 6 7 2    4 1 3 5 8 6    7 2 4 1 3 5    8 6 7 2 4 1

随机播放每个列表

7 3 5 6 2 8    1 3 4 8 6 5    3 4 1 5 7 2    2 7 4 1 8 6

随机播放列表列表

1 3 4 8 6 5    2 7 4 1 8 6    7 3 5 6 2 8    3 4 1 5 7 2

该程序

该程序应该可以在 Java 7 中运行。但是我只使用 Java 11 对其进行了测试。

import java.util.*;
public class Shuffle {
    public static void main(String[] args) {
        System.out.println(splitShuffle(Arrays.asList(1,2,3,4,5,6,7,8), 6, 3));
    }
    public static List<List<Integer>> splitShuffle(
            List<Integer> input, int newLength, int listCount) {        
        assert newLength * listCount % input.size() == 0 : "Cannot distribute numbers evenly";
        input = new ArrayList<>(input);
        Collections.shuffle(input);
        List<List<Integer>> result = new ArrayList<>(listCount);
        for (int i = 0; i < listCount; ++i) {
            result.add(rotatingCopy(input, i * newLength, newLength));
        }
        Collections.shuffle(result);
        return result;
    }
    private static List<Integer> rotatingCopy(List<Integer> input, int startIndex, int length) {
        assert length < input.size() : "copy would have to contain duplicates";
        List<Integer> copy = new ArrayList<>(length);
        for (int i = 0; i < length; ++i) {
            copy.add(input.get((startIndex + i) % input.size()));
        }
        Collections.shuffle(copy);
        return copy;
    }
}

示例输出

我运行了四次程序。 这是它的输出。 每一行都是程序的一次运行。

[[2, 6, 7, 8, 1, 3], [4, 3, 7, 5, 2, 8], [1, 2, 6, 5, 4, 8]]
[[2, 7, 5, 4, 6, 1], [4, 7, 2, 6, 8, 3], [1, 3, 5, 8, 6, 4]]
[[4, 1, 2, 5, 6, 3], [5, 3, 8, 4, 6, 7], [5, 1, 2, 7, 3, 8]]
[[5, 3, 8, 2, 6, 4], [1, 7, 4, 5, 6, 3], [1, 6, 2, 8, 7, 4]]

正如我们所看到的,每个数字恰好出现两次,每个子列表只有唯一的数字。

完整性

至少对于输入列表[1, 2, 3]y=3, z=2我可以验证是否可以生成所有可能的 48 个输出。 我知道使用以下 bash 命令有 48 种组合:

printf %s\\n {1..3}{1..3},{1..3}{1..3},{1..3}{1..3} | grep -Pv '(\d)\1' |
tr -d , | awk '{print $1, gsub(1,""), gsub(2,""), gsub(3,"")}' |
grep -F ' 2 2 2' | cut -d' ' -f1 | sort -u | wc -l
回答3

我的方法是打乱原始列表,然后不断迭代直到填充目标列表,然后打乱每个目标列表。 这将使每个数字的出现保持平衡。 如果numbersPerCombination > numbers.size()它也有效。

public class FairLists {

    public static void main(String[] args) {
        List<Integer> numbers = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8);
        List<List<Integer>> fairLists = getOptimizedCombinations(numbers, 6, 3);
        System.out.println(fairLists);
    }

    public static List<List<Integer>> getOptimizedCombinations(List<Integer> numbers, int numbersPerCombination, int desiredCombinations){
        List<Integer> source = new ArrayList<>(numbers);
        Collections.shuffle(source);

        List<List<Integer>> fairNumbersLists = new ArrayList<>(desiredCombinations);

        int sourceIndex = 0;
        while (desiredCombinations > 0) {

            List<Integer> fairNumbers = new ArrayList<>(numbersPerCombination);
            for (int i = 0; i < numbersPerCombination; i++) {
                fairNumbers.add(source.get(sourceIndex));
                sourceIndex++;
                if (sourceIndex == source.size()) {
                    sourceIndex = 0;
                }
            }

            Collections.shuffle(fairNumbers);
            fairNumbersLists.add(fairNumbers);

            desiredCombinations--;
        }

        Collections.shuffle(fairNumbersLists);
        return fairNumbersLists;
    }
}
回答4

在我们聊天期间,您要求我编写有关组合的代码,所以这不是您问题的答案,只是您可以探索的代码

public class Combination {

    private Combination() {
    }

    /**
     *
     * @param n:
     *            n-set
     * @param m:
     *            m-subset
     * @return number of combinations C(n, m) = (n(n - 1)...(n - m + 1)) / m!
     */
    public static BigInteger C(int n, int m) {
        if (m > n) {
            return BigInteger.ZERO;
        } else {
            if ((n - m) > m) {
                return C(n, (n - m));
            }
        }
        BigInteger numerator = BigInteger.ONE;
        BigInteger denominator = BigInteger.ONE;

        for (int i = n; i > m; i--) {
            numerator = numerator.multiply(BigInteger.valueOf(i));
        }

        for (int i = (n - m); i > 1; i--) {
            denominator = denominator.multiply(BigInteger.valueOf(i));
        }

        return numerator.divide(denominator);
    }

    /**
     *
     * @param <T>
     *            Type
     * @param elements
     *            List of elements to combine
     * @param numberOfRequiredElements
     *            must be less or equal to elements.size()
     * @param combinatios
     *            result: List&lt;List&lt;T&gt;&gt; of all combinations
     * @param temp
     *            used for recursive purposes
     * @return combinations<br>
     * 
     *         Example of usage:<br>
     *         List&lt;Integer&gt; elements = new ArrayList&lt;&gt;();<br>
     *         for (int i = 1; i &lt;= 7; i++) {<br>
     *         &emsp;elements.add(i);<br>
     *         }<br>
     *         List&lt;Integer&gt; temp = new ArrayList&lt;&gt;();<br>
     *         List&lt;List&lt;Integer&gt;&gt; combinations = new
     *         ArrayList&lt;&gt;();<br>
     *         System.out.println(Combination.allCombinations(elements, 6,
     *         combinations, temp));<br>
     *
     */
    public static <T> List<List<T>> allCombinations(List<T> elements, int numberOfRequiredElements,
            List<List<T>> combinatios, List<T> temp) {
        if (numberOfRequiredElements == 0) {
            // System.out.print(temp);
            combinatios.add(new ArrayList<>(temp));
        } else {
            for (int i = 0; i < elements.size(); i++) {
                temp.add(elements.get(i));
                List<T> subList = elements.subList(i + 1, elements.size());
                allCombinations(subList, numberOfRequiredElements - 1, combinatios, temp);
                temp.remove(temp.size() - 1);
            }
        }
        return combinatios;
    }

    /**
     *
     * @param args
     *            Not required for this purpose
     */
    public static void main(String[] args) {
        int NO_OF_ELEMENS = 10;
        int REQURED_COMBINATION_SIZE = 6;

        List<Integer> elements = new ArrayList<>();
        for (int i = 1; i <= NO_OF_ELEMENS; i++) {
            elements.add(i);
        }
        System.out.println("This is an example of using methods in this class\n");
        System.out.println("Elements are " + elements + " (size = " + elements.size() + ")");
        System.out.println("Requred size of combination is " + REQURED_COMBINATION_SIZE);
        System.out.println("Number of all combinations is " + Combination.C(NO_OF_ELEMENS, REQURED_COMBINATION_SIZE));
        List<Integer> temp = new ArrayList<>();
        List<List<Integer>> combinations = new ArrayList<>();
        System.out.println("All combinations are:");
        Combination.allCombinations(elements, REQURED_COMBINATION_SIZE, combinations, temp);
        int i = 0;
        for (List<Integer> combination : combinations) {
            System.out.println(++i + "\t" + combination);
        }
    }
}

我希望这段代码能有所帮助。 PS 对无法阅读的评论感到抱歉 - 我之前在 NetBeans 中写过这个,现在我正在使用 IntelliJ ......

编辑:使用 long 而不是BigInteger来计算组合数...(就个人而言,我不推荐这样做)。

public static long noOfCombinations(int n, int m){

    //this part is for fewer multiplications
    //b/c 4 out of 6 has the same number of combinations as 2 out of 6
    if (m > n) {
        return 0;
    } else {
        if ((n - m) > m) {
            return noOfCombinations(n, (n - m));
        }
    }

    long numerator = 1;
    long denominator = 1;

    //these two loops are for partial factorial
    for (int i = n; i > m; i--) {
        numerator *= i;
    }

    for (int i = (n - m); i > 1; i--) {
        denominator *= i;
    }

    // no of combinations
    return numerator / denominator;
}

受限制的 HTML

  • 允许的HTML标签:<a href hreflang> <em> <strong> <cite> <blockquote cite> <code> <ul type> <ol start type> <li> <dl> <dt> <dd> <h2 id> <h3 id> <h4 id> <h5 id> <h6 id>
  • 自动断行和分段。
  • 网页和电子邮件地址自动转换为链接。

相关推荐
  • 用于在现场并使用O(1)内存打印混洗的列表的算法(Algorithm to print out a shuffled list, in-place and with O(1) memory)
    问题 阅读了这个问题后,我开始怀疑:是否有可能采用一种不修改或复制原始列表的改组算法? 明确说明: 想象一下,您得到了一个对象列表。 列表大小可以是任意的,但假定它很大(例如10,000,000个项目)。 您需要以随机顺序打印出列表中的项目,并且需要尽快进行打印。 但是,您不应: 复制原始列表,因为它很大,复制会浪费很多内存(可能会超出可用RAM的限制); 修改原始列表,因为它是以某种方式排序的,以后的其他部分取决于它的排序方式。 创建索引列表,因为该列表又很大,并且复制占用了太多时间和内存。 (澄清:这表示其他任何列表,其元素数与原始列表相同)。 这可能吗? 补充:更多说明。 我希望列表以真正随机的方式进行混洗,所有排列的可能性均相同(当然,假设我们有一个合适的Rand()函数开始)。 我提出的一个指针列表,一个索引列表或任何其他元素列表数量与原始列表相同的建议,被原始问题明确认为是无效的。 您可以根据需要创建其他列表,但是它们应比原始列表小几个数量级。 原始列表就像一个数组,您可以通过O(1)中的索引从其中检索任何项目。 (因此,没有双向链接的列表内容,您必须在列表中进行迭代才能找到所需的项目。) 添加2 :好,让我们这样说:您有一个1TB的HDD,其中填充了数据项,每个数据项大512字节(一个扇区)。 您想在将所有项目混排的同时将所有这些数据复制到另一个1TB HDD。
  • 您如何有效地生成一个介于0和上限N之间的K个非重复整数的列表[重复](How do you efficiently generate a list of K non-repeating integers between 0 and an upper bound N [duplicate])
    问题 这个问题已经在这里有了答案: O(1)中的唯一(非重复)随机数? (22个答案) 4年前关闭。 这个问题给出了所有必要的数据:在给定的时间间隔[0,N-1]内生成K个非重复整数序列的有效算法是什么? 如果K很大并且足够接近N,那么琐碎的算法(生成随机数,然后将它们添加到序列中之前先查找它们,以查看它们是否已经存在)是非常昂贵的。 从链接列表中有效地选择一组随机元素中提供的算法似乎比必需的更为复杂,并且需要一些实现。 只要您知道所有相关参数,我就找到了另一种似乎可以很好地完成工作的算法。 回答1 Python库中的random模块使它极其简单和有效: from random import sample print sample(xrange(N), K) sample函数返回从给定序列中选择的K个唯一元素的列表。 xrange是一个“列表仿真器”,即它的行为就像一个连续数字的列表,而没有在内存中创建它,这使得它非常快地执行此类任务。 回答2 Knuth在《计算机编程艺术》,第2卷:《半数值算法》,第三版中描述了以下选择采样算法: 算法S(选择采样技术)。 从一组N中随机选择n条记录,其中0 <n≤N。 S1。 [初始化。]设置t←0,m←0。(在此算法中,m表示到目前为止选择的记录数,而t是我们处理过的输入记录的总数。) S2。 [生成U。]生成一个随机数U
  • 生成[0,8000]范围内的1000个不同整数的算法? [复制](Algorithm to generate 1000 distinct integers in the range [0,8000]? [duplicate])
    问题 这个问题已经在这里有了答案: 8年前关闭。 可能重复: 如何有效地生成0到上限N之间的K个非重复整数的列表 有什么替代方法可以生成1000个[0,8000]范围内的不同随机整数,而不是以下内容: 天真的方法:生成一个数字并检查它是否已经在数组中。 O(n ^ 2) 线性混洗:生成序列0到8000,混洗,取前1000。O(n) 回答1 您可以使用通过交换实现的部分Fisher-Yates随机播放。 该算法的一个不错的功能是,如果在k交换之后停止,则前k数字是完整集中大小为k的随机样本。 回答2 您可以创建一个包含数字0到8000的列表。 然后循环1000次会生成一个介于0和列表长度之间的随机数。 从列表中删除该元素,然后将其添加到输出列表中。 通过删除元素,可以确保您的选择是唯一的。 while (outputList.Count < 1000) { index = random.Next(0, inputList.Count); outputList.Add(inputList[index]); inputList.RemoveAt(index); } 回答3 这来自Knuth的《编程艺术》(通过Jon Bentley的《 Programming Pearls》),该语言以Python实现: import random # randomly select m numbers
  • 用C语言编程的整数数组中的唯一随机数(Unique random numbers in an integer array in the C programming language [duplicate])
    问题 这个问题已经在这里有了答案: 8年前关闭。 可能重复: O(1)中的唯一随机数? 如何在C中使用唯一值(无重复项)填充整数数组? int vektor[10]; for (i = 0; i < 10; i++) { vektor[i] = rand() % 100 + 1; } //No uniqueness here 回答1 解决问题的方法有多种,每种都有其优点和缺点。 首先,我想指出的是,您已经获得了很多响应,它们执行以下操作:它们生成一个随机数,然后以某种方式检查它是否已在数组中使用,如果已经使用过,则仅生成另一个编号,直到找到未使用的编号为止。 这是一种幼稚的方法,说实话,是一种严重错误的方法。 问题在于数字生成的循环反复试验性质(“如果已使用,请重试”)。 如果数值范围(例如[1..N])接近所需数组的长度(例如M),那么到最后,算法可能会花费大量时间来尝试查找下一个数字。 如果随机数生成器甚至有点破损(例如,从不生成某个数字,或者很少生成),那么使用N == M可以保证算法永远循环(或循环很长时间)。 通常,这种反复试验方法无用或充其量是有缺陷的。 这里已经介绍的另一种方法是在大小为N的数组中生成随机排列。随机排列的想​​法是一种很有前途的方法,但是在大小为N的数组上进行排列(当M << N时,肯定会产生比光更多的热量) ,比喻地说。 例如,可以在Bentley的
  • 使用Random和OrderBy是一种很好的随机播放算法吗?(Is using Random and OrderBy a good shuffle algorithm?)
    问题 我在Coding Horror上阅读了有关各种随机播放算法的文章。 我已经看到有人在这样做以随机排列列表: var r = new Random(); var shuffled = ordered.OrderBy(x => r.Next()); 这是一个很好的随机播放算法吗? 究竟如何运作? 这是可以接受的方式吗? 回答1 这不是我喜欢的一种改组方式,主要是因为它很容易实现O(n)改组,因此没有充分的理由是O(n log n)。 问题“工作”中的代码基本上是为每个元素赋予一个随机(希望是唯一的!)数字,然后根据该数字对元素进行排序。 我更喜欢Durstenfield的Fisher-Yates shuffle的变体,它可以交换元素。 实现一个简单的Shuffle扩展方法主要包括在输入上调用ToList或ToArray ,然后使用Fisher-Yates的现有实现。 (将Random作为参数传递,以使生活更美好。)周围有很多实现方式……我可能在某个地方给出了答案。 这种扩展方法的好处是,读者可以很清楚地知道您实际上正在尝试做什么。 编辑:这是一个简单的实现(没有错误检查!): public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> source, Random rng) { T[] elements = source
  • Minhash算法需要多少个哈希函数(How many hash functions are required in a minhash algorithm)
    问题 我热衷于尝试实施minhashing以查找几乎重复的内容。 http://blog.cluster-text.com/tag/minhash/写的很好,但是这里的问题是,为了获得合理的结果,您需要在文档中的带状疱疹上运行多少个哈希算法。 上面的博客文章提到了200种哈希算法。 http://blogs.msdn.com/b/spt/archive/2008/06/10/set-similarity-and-min-hash.aspx将100列为默认值。 显然,随着散列数量的增加,准确性也有所提高,但是多少个散列函数是合理的呢? 引用博客 很难使我们的相似性估计值的误差线小得多[7%],这是因为统计采样值刻度上的误差线的方式-将误差线切成两半,我们将需要四倍的样本量。 这是否意味着将散列数量减少到12(200/4/4)左右会导致28%的错误率(7 * 2 * 2)? 回答1 差不多..但是28%是“误差估计”,这意味着报告的测量值经常不准确+/- 28%。 这意味着所报告的78%的度量很容易仅来自50%的相似性。或者50%的相似性很容易被报告为22%。 对我来说,听起来不够准确,无法满足业务期望。 从数学上讲,如果要报告两位数,则第二位应该有意义。 为什么要将哈希函数的数量减少到12个? “ 200个散列函数”的真正含义是,为每个带状疱疹/字符串一次计算一个质量不错的散列码
  • 使用随机数生成器对整数进行随机排列(Random permutation of integers using a random number generator)
    问题 这是我的作业: Random r = new Random(); public int get100RandomNumber() { return 1+r.nextInt(100); } 您将获得一个名为getrand100()的预定义函数(上面),该函数返回一个整数,该整数是1到100之间的一个随机数。 您可以根据需要多次调用此函数,但是请注意,此函数会占用大量资源。 您不能使用任何其他随机生成器。 您不能更改getrand100()的定义。 输出:以随机顺序打印数字1-20。 (不是20个随机数) 我尝试过的.. public class MyClass { static Random r = new Random(); static HashSet<Integer>; public static void main(String args[]) { myMethod(); System.out.println(s); } public static void myMethod() { boolean b = false; s = new HashSet<Integer>(); int i = getRand100(); if (i >= 20) i = i % 20; int j = 0; int k, l; while (s.size() <= 20) {
  • 使用密钥的可逆随机播放算法(Reversible shuffle algorithm using a key)
    问题 我该如何在C#中编写一种可逆的随机播放算法,该算法使用密钥进行随机播放并可以恢复为原始状态? 例如,我有一个字符串:“ Hello world”,如何对其进行混洗,以便以后可以将经过混洗的字符串反向转换为“ Hello world”。 回答1 查看费舍尔-耶茨(Fisher-Yates)随机播放,以了解一种根据密钥对字符串进行置换的方法。 将密钥作为种子输入PRNG,使用该密钥生成随机播放的随机数。 现在,如何逆转该过程? Fisher-Yates通过交换某些元素对来工作。 因此,为了反转该过程,您可以将相同的键输入到相同的PRNG中,然后通过Fisher-Yates算法运行,就好像您在对字符串大小的数组进行混洗一样。 但是实际上您什么也没动,只要记录下将在每个阶段交换的元素的索引即可。 完成此操作后,请按相反顺序浏览交换列表,并将其应用于混洗后的字符串。 结果是原始字符串。 因此,例如,假设我们使用以下交换对字符串“ hello”进行了混洗(我在这里没有使用PRNG,我掷骰子,但是关于PRNG的要点是,给定相同的数字序列种子): (4,0): "hello" -> "oellh" (3,3): "oellh" -> "oellh" (2,1): "oellh" -> "olelh" (1,0): "olelh" -> "loelh" 因此,改组后的字符串为“ loelh”。
  • 从集合中选择随机子集的最佳方法?(best way to pick a random subset from a collection?)
    问题 我在Vector中有一组对象,可以从中选择一个随机子集(例如,返回100个项目;随机选择5个项目)。 在我的第一遍(非常仓促)中,我做了一个非常简单甚至过于聪明的解决方案: Vector itemsVector = getItems(); Collections.shuffle(itemsVector); itemsVector.setSize(5); 尽管这样做的好处是简单好用,但我怀疑它的伸缩性不会很好,即Collections.shuffle()至少必须为O(n)。 我不太聪明的选择是 Vector itemsVector = getItems(); Random rand = new Random(System.currentTimeMillis()); // would make this static to the class List subsetList = new ArrayList(5); for (int i = 0; i < 5; i++) { // be sure to use Vector.remove() or you may get the same item twice subsetList.add(itemsVector.remove(rand.nextInt(itemsVector.size()))); }
  • 在总和匹配的两组整数中查找子集的算法(Algorithm to find subset within two sets of integers whose sums match)
    问题 我正在寻找一种算法,它可以采用两组整数(正整数和负整数)并在每个整数中找到具有相同总和的子集。 该问题类似于子集求和问题,只是我正在寻找双方的子集。 下面是一个例子: 列表 A {4, 5, 9, 10, 1} 列表 B {21, 7, -4, 180} 所以这里唯一的匹配是:{10, 1, 4, 9} <=> {21, 7, -4} 有谁知道这种问题是否有现有的算法? 到目前为止,我唯一的解决方案是尝试每种组合的蛮力方法,但它在指数时间内执行,我不得不对要考虑的元素数量进行严格限制,以避免花费太长时间。 我能想到的唯一其他解决方案是在两个列表上运行阶乘并在那里寻找相等性,但这仍然不是很有效,并且随着列表变大,所需的时间呈指数级增长。 回答1 其他人说的是真的: 这个问题是NP完全的。 一个简单的减少是通常的子集总和。 您可以通过注意 A 的子集和 B 的子集(不是都为空)仅当 A 联合 (-B) 的非空子集和为零时来证明这一点。 这个问题只是弱 NP 完全的,因为它在所涉及的数字的大小上是多项式,但据推测它们的对数是指数的。 这意味着该问题比名称“NP-complete”可能暗示的更容易。 您应该使用动态规划。 那么我对这个讨论有什么贡献呢? 好吧,代码(在 Perl 中): @a = qw(4 5 9 10 1); @b = qw(21 7 -4 180); %a =
  • 以随机顺序迭代具有相同数量的 1(或 0)的二进制数(Iterate binary numbers with the same quantity of ones (or zeros) in random order)
    问题 我需要以随机顺序生成具有相同数量的 1(或 0)的二进制数。 有谁知道固定长度二进制数的任何有效算法? 2 位和 4 位数字的示例(为了更清楚): 1100 1010 1001 0110 0101 0011 更新无重复的随机顺序很重要。 需要二进制数的序列,而不是单个排列。 回答1 如果您有足够的内存来存储所有可能的位序列,并且您不介意在获得第一个结果之前将它们全部生成,那么解决方案是使用一些高效的生成器将所有可能的序列生成为一个向量,然后进行洗牌使用 Fisher-Yates shuffle 的向量。 这很容易而且没有偏见(只要你使用一个好的随机数生成器来进行随机数),但如果n很大,它会使用大量内存,特别是如果你不确定是否需要完成迭代。 但是有几种解决方案不需要将所有可能的单词保留在内存中。 (这两种解决方案的 C 实现遵循文本。) 1. Bit shuffle 枚举 最快的(我认为)是首先生成位值的随机混洗,然后一次一个地迭代可能的单词,将混洗应用于每个值的位。 为了避免混洗实际位的复杂性,可以按格雷码顺序生成字,其中从一个字到下一个字只改变两个位位置。 (这也称为“旋转门”迭代,因为每添加一个新的1就必须删除其他一些1 )这允许快速更新位掩码,但这意味着连续的条目高度相关,这可能不适合某些用途。 此外,对于较小的n值,可能的比特混洗次数非常有限
  • 每次只返回一个数字的随机数生成器(Random number generator that returns only one number each time)
    问题 Python 是否有一个随机数生成器,每次调用next()函数时只返回一个随机整数? 数字不应重复,生成器应返回区间[1, 1 000 000]内唯一的随机整数。 我需要生成超过一百万个不同的数字,这听起来好像非常消耗内存,以防所有数字同时生成并存储在列表中。 回答1 您正在寻找具有完整周期的线性同余生成器。 这将允许您在目标数字范围内获得非重复数字的伪随机序列。 实现一个 LCG 其实很简单,看起来像这样: def lcg(a, c, m, seed = None): num = seed or 0 while True: num = (a * num + c) % m yield num 然后,它只是为a 、 c和m选择正确的值以保证 LCG 将生成一个完整的周期(这是您获得非重复数字的唯一保证)。 正如维基百科文章所解释的,需要满足以下三个条件: m和c需要互质。 a - 1可以被m所有质因数整除 a - 1能被 4 整除,如果m也能被 4 整除。 第一个很容易通过简单地为c选择一个素数来保证。 此外,这是可以最后选择的值,这最终将允许我们稍微混淆序列。 但是a - 1和m之间的关系更复杂。 在完整的周期 LCG 中, m是周期的长度。 或者换句话说,它是您的数字来自的数字范围。 所以这就是你通常首先选择的。 在您的情况下,您希望m大约为1000000 。
  • c# - 如何在保持内部顺序的同时将2个已排序的列表合并到一个混洗列表中(How to merge 2 sorted listed into one shuffled list while keeping internal order in c#)
    问题 我想生成一个混洗的合并列表,以保持列表的内部顺序。 例如: 列表 A:11 22 33 列表 B:6 7 8 有效结果: 11 22 6 33 7 8 无效结果:22 11 7 6 33 8 回答1 原答案: static IEnumerable<T> MergeShuffle<T>(IEnumerable<T> lista, IEnumerable<T> listb) { var first = lista.GetEnumerator(); var second = listb.GetEnumerator(); var rand = new Random(); bool exhaustedA = false; bool exhaustedB = false; while (!(exhaustedA && exhaustedB)) { bool found = false; if (!exhaustedB && (exhaustedA || rand.Next(0, 2) == 0)) { exhaustedB = !(found = second.MoveNext()); if (found) yield return second.Current; } if (!found && !exhaustedA) { exhaustedA = !(found = first
  • 选择单个,随机值组合的算法?(Algorithm to select a single, random combination of values?)
    问题 假设我有y不同的值,我想随机选择其中的x 。 有什么有效的算法可以做到这一点? 我可以调用rand() x次,但是如果x , y大,则性能会很差。 请注意,这里需要组合:每个值应具有相同的概率被选择,但是它们在结果中的顺序并不重要。 当然,任何生成置换的算法都符合条件,但我想知道是否有可能在没有随机顺序要求的情况下更有效地做到这一点。 如何有效地生成0到上限N之间的K个非重复整数的列表,涵盖了这种排列的情况。 回答1 罗伯特·弗洛伊德(Robert Floyd)为此发明了一种采样算法。 由于不需要O(y)存储,因此它通常比改组然后获取前x元素更好。 如最初所写,它假定值从1..N开始,但是通过简单地将其产生的值作为下标处理到向量/数组/任何对象中,产生0..N和/或使用非连续值是微不足道的。 在pseuocode中,算法的运行方式是这样的(从Jon Bentley的Programming Pearls专栏“ Brillance of Brilliance”中窃取)。 initialize set S to empty for J := N-M + 1 to N do T := RandInt(1, J) if T is not in S then insert T in S else insert J in S 最后一点(如果T已经在S中,则插入J)是棘手的部分。 最重要的是
  • 创建无重复的随机数序列(Create Random Number Sequence with No Repeats)
    问题 复制: O(1)中的唯一随机数? 我想要一个伪随机数生成器,它可以生成没有随机顺序重复的数字。 例如: 随机的(10) 可能返回5、9、1、4、2、8、3、7、6、10 除了确定数字范围并将其改组或检查生成的列表是否重复之外,还有其他更好的方法吗? 编辑: 我也希望它能在没有整个范围的情况下有效地生成大数字。 编辑: 我看到每个人都在建议改组算法。 但是,如果我想生成一个较大的随机数(1024字节+),那么与仅使用常规RNG并将其插入Set中直到达到指定的长度相比,该方法将占用更多的内存,对吗? 没有更好的数学算法可以做到这一点。 回答1 您可能对线性反馈移位寄存器感兴趣。 我们以前是用硬件来构建它们的,但是我也已经用软件来完成它们。 它使用移位寄存器,将某些位进行异或并反馈到输入,如果您选择正确的“抽头”,则可以获得与寄存器大小一样长的序列。 也就是说,一个16位的lfsr可以产生一个65535长的序列,没有重复。 它在统计上是随机的,但当然可以重复。 另外,如果做错了,您可以得到一些令人尴尬的短序列。 如果您查找lfsr,将找到有关如何正确构造它们(即“最大长度”)的示例。 回答2 随机播放是执行此操作的绝佳方法(前提是您不使用朴素算法引入偏差)。 请参阅Fisher-Yates随机播放。 回答3 为了确保该列表不会重复,它必须保留以前返回的数字的列表。 因此
  • 什么是排序列表项的好的 CRUD 同情算法?(What is a good, CRUD-sympathetic algorithm for ordering list items?)
    问题 我想要一种简单的方法来表示对象列表的顺序。 当对象在该列表中更改位置时,我只想更新一条记录。 我不知道这是否可以完成,但我有兴趣问问 SO hive ...... 愿望清单限制 算法(或数据结构)应该允许通过更新单个项目的属性来重新定位列表中的项目算法(或数据结构)应该不需要内务来维护列表的完整性算法(或数据结构)应允许插入新项目或删除现有项目 为什么我关心一次只更新一个项目... [更新以澄清问题] 该算法的用例是具有 CRUDy、资源丰富的服务器设置和干净(Angular)客户端的 Web 应用程序。 在可能的情况下保持纯 CRUD 操作是一种很好的做法,并且可以使代码更加清晰。 如果我可以在单个resource#update请求中执行此操作,那么我不需要任何额外的服务器端代码来处理重新排序,并且所有这些都可以使用 CRUD 完成而无需更改。 如果每次移动都需要更新列表中的多个项目,那么我需要在控制器上执行一个新操作来处理它。 它不是一个引人注目的东西,但它开始蔓延到 Angular 中,一切都变得不那么干净了。 例子 假设我们有一本杂志,该杂志有很多页: Original magazine - double page advert for Ford (page=1) - article about Jeremy Clarkson (page=2) - double
  • O(1)中的唯一(非重复)随机数?(Unique (non-repeating) random numbers in O(1)?)
    问题 我想生成一个介于0到1000之间的永不重复的唯一随机数(即6不会出现两次),但是这并不能求助于像O(N)那样搜索以前的值来做到这一点。 这可能吗? 回答1 使用0-1000值初始化1001个整数的数组,并将变量max设置为数组的当前max索引(从1000开始)。 选择一个介于0到max之间的随机数r,将r处的数字与max处的数字交换,然后立即将其返回max处的数字。 最大减1,然后继续。 当max为0时,将max设置回数组的大小-1,然后重新启动,而无需重新初始化数组。 更新:尽管我在回答问题时自行提出了这种方法,但经过一些研究,我意识到这是费舍尔·耶茨(Fisher-Yates)的改进版本,称为Durstenfeld-Fisher-Yates或Knuth-Fisher-Yates。 由于描述可能会有些困难,因此我在下面提供了一个示例(使用11个元素而不是1001): 数组以初始化为array [n] = n的11个元素开始,最大值从10开始: +--+--+--+--+--+--+--+--+--+--+--+ | 0| 1| 2| 3| 4| 5| 6| 7| 8| 9|10| +--+--+--+--+--+--+--+--+--+--+--+ ^ max 在每次迭代中,从0到max之间选择一个随机数r,将array [r]和array [max]交换
  • 这些算法中哪一个在生成 1..n 范围内的 N 个唯一随机数的性能和顺序上更好?(Which of these algorithm is better in performance and order for generating N unique random number in 1..n range?)
    问题 1 取一个包含 n 个元素的数组:{ 1, 2, 3, .... n }。 使用随机混洗数组的任何标准算法对数组进行混洗。 修改后的数组的前 N ​​个元素就是您要查找的内容。 2 只需在循环中使用Random.Next()并检查它是否已经存在于Dictionary ,直到我们有 N 个数字。 请注意, N << n ( N 非常小于 n) 回答1 部分Fisher-Yates,有一些调整*: 在 [0,8000] 范围内生成 1000 个不同整数的算法? & 选择单个随机值组合的算法? * 这里的主要内容是减少了内存使用量,因此它现在与最多选择的项目数成正比,而不是与可选择的项目数成正比。 如果N << n (如您所提到的),这可以节省大量资金。 (空间使用上限为 O(n/2),无论 N 与 n 有多接近。) 运行时间为 O(N)。 除此之外,这是一个相当常见的部分Fisher-Yates,又名Knuth shuffle。 回答2 这两个都不是最好的。 你需要一个Fisher-Yates shuffle。 随机解决方案的问题在于您预先做了很多不必要的工作。 第二种解决方案的问题是重复的机会随着时间的推移变得更高,因此您会丢弃很多值。 对于一个非常有效的解决方案,它可以为您提供一个重复可能性为零的值子集(并且没有不必要的预先排序),Fisher-Yates 是要走的路。
  • 按总和的顺序生成 k 个元素子集的算法(Algorithm to generate k element subsets in order of their sum)
    问题 如果我有一个未排序的大集合n整数(比如2^20个),并且想生成具有k元素的子集(其中k很小,比如5 )以它们的总和递增的顺序,什么是最有效的方法这样做? 为什么我需要以这种方式生成这些子集是因为我想找到满足某个条件的最小和的 k 元素子集,因此我会将条件应用于生成的每个 k 元素子集。 另外,算法的复杂度是多少? 这里有一个类似的问题:Algorithm to get every possible subset of a list, in order of their product, without building and sort the entire list (ie Generators) about generated subs of their product,但它不适合我由于集合n的极大尺寸需要 我打算在 Mathematica 中实现该算法,但也可以在 C++ 或 Python 中实现。 回答1 如果您想要的小子集的属性(称为P )相当普遍,则概率方法可能效果很好: 对n整数进行排序(对于数百万个整数,即 10 到 100 MB 的 ram,这应该不是问题),并将k-1最小值相加。 将此称为总offset 。 生成一个随机k集(例如,通过对k随机数进行采样,mod n )并检查它的P 。 在比赛中,记下子集的总和。
  • 迭代具有相同总和的固定大小正整数列表的算法(algorithm to iterate through fixed size positive integer lists with the same sum)
    问题 我正在寻找一种快速且内存高效的算法来迭代具有给定总和 (N) 的相同大小 (S) 的所有可能的正整数列表。 例如,如果 S = 3 和 N = 4 结果将是(我有一个非常低效的算法): [0, 0, 4] [0, 1, 3] [0, 2, 2] [0, 3, 1] [0, 4, 0] [1, 0, 3] [1, 1, 2] [1, 2, 1] [1, 3, 0] [2, 0, 2] [2, 1, 1] [2, 2, 0] [3, 0, 1] [3, 1, 0] [4, 0, 0] 不一定按这个顺序。 另一种看待它的方式是如何将数字 N 切成 S 块。 如果我还可以为列表中的每个单独值设置最大值,则该算法将是完美的。 我将使用它以与product(*indices)生成的顺序不同的顺序运行多维数组。 同时生成所有索引组合并按总和对它们进行排序会太慢/消耗内存。 回答1 找到了一个解决方案:它基于这样一个想法,即正数 N 是一行单位,将它们分成 S 块是将 (S-1) 分隔符放在列表中的问题。 这些分隔符可以使用combinations(range(N + S - 1), S - 1)进行迭代。 下一步是计算分隔符之前、之间和之后的单位数: def partition(N, size): n = N + size - 1 for splits in combinations