随机生成一个数组中的-1或1序列

Question

需要在for循环的每一步打印旋转配置所以对于n = 4配置，我们可以

 1     1    1     1            
 1     1   -1     1           
-1     1   -1     1           
-1     1   -1     1            
-1    -1   -1     1  

我需要随机生成1或-1，如果n = 4，则长度为4的数组为1或-1，在这种情况下，最多可以有2 ^ n ^ ^ 4可能的配置。需要打印出这些可能的配置。不知道怎么回事？任何帮助，将不胜感激。谢谢

import java.util.Random;

public class RandomTest {

    public static void main(String[] args) {
        for (int i = 0; i < 4; i++) {
            System.out.println(randomOneOrMinusOne());

        }
    }

    static int randomOneOrMinusOne() {
        Random rand = new Random();
        if (rand.nextBoolean())
            return 1;
        else
            return -1;
    }
}

Answer 1

这通过遍历2 ^ n个组合中的每一个来查看组合中的哪些位被设置。如果设置了一个位，则在数组中加“1”，否则输入“-1”。

import java.math.BigInteger;
import java.util.Arrays;

public class AllSeq {

    public static void main(String[] args) {
        // Get the number of elements from args or default to 4
        int n = args.length > 0 ? Integer.parseInt(args[0]) : 4;

        // Work out total number of combinations (2^n)
        BigInteger combinations = BigInteger.valueOf(2).pow(n);

        // For each combination...
        for(BigInteger i = BigInteger.ZERO; i.compareTo(combinations) < 0; i = i.add(BigInteger.ONE)) {
            // Initialise an array with 'n' elements
            int[] resultForThisCombination = new int[n];

            // We now go through each bit in the combination...
            for(int bit = 0; bit < n; bit++) {
                BigInteger bitValue = BigInteger.valueOf(2).pow(bit);

                // If the bit is set, set array element to 1 else set it to -1...
                if(i.and(bitValue).equals(bitValue)) {
                    resultForThisCombination[bit] = 1;
                } else {
                    resultForThisCombination[bit] = -1;
                }
            }

            // Print result / do whatever with it
            System.out.println(Arrays.toString(resultForThisCombination));
        }
    }
}

如果你为n输入一个大数字，你可能会等待一段时间......

如果n不超过63（如果你想等那么久!!），你可以使用long而不是BigInteger。

Answer 2

class Solution {
    public static void main(String[] args) {
        List<List<Integer>> result = generateSequences(4);
        for(int i=0;i<result.size();++i){
            System.out.println(result.get(i).toString());
        }
    }

    private static List<List<Integer>> generateSequences(int seq_size){
        List<List<Integer>> result = new ArrayList<List<Integer>>();

        // for our recursion base case
        if(seq_size == 1){
            List<Integer> new_seq_1 = new ArrayList<>(); // add -1 once 
            new_seq_1.add(-1);
            List<Integer> new_seq_2 = new ArrayList<>(); // add 1 once
            new_seq_2.add(1);
            result.add(new_seq_1);
            result.add(new_seq_2);
            return result;
        }

        List<List<Integer>> sub_ans = generateSequences(seq_size - 1);

        for(int i=0;i<sub_ans.size();++i){
            List<Integer> new_seq_1 = new ArrayList<>(sub_ans.get(i)); // add -1 once 
            new_seq_1.add(-1);
            List<Integer> new_seq_2 = new ArrayList<>(sub_ans.get(i)); // add 1 once
            new_seq_2.add(1);
            result.add(new_seq_1);
            result.add(new_seq_2);
        }

        return result;
    }
}

输出：

[-1, -1, -1, -1]
[-1, -1, -1, 1]
[-1, -1, 1, -1]
[-1, -1, 1, 1]
[-1, 1, -1, -1]
[-1, 1, -1, 1]
[-1, 1, 1, -1]
[-1, 1, 1, 1]
[1, -1, -1, -1]
[1, -1, -1, 1]
[1, -1, 1, -1]
[1, -1, 1, 1]
[1, 1, -1, -1]
[1, 1, -1, 1]
[1, 1, 1, -1]
[1, 1, 1, 1]

算法：

• 我们可以递归地做到这一点。
• 因此，对于每个位置，我们可以得到-1或1.因为你想要所有可能的序列，我们需要取-1和1。
• 因此，如果大小是1，2的可能性是[-1]和[1]。
• 让我们通过一个例子来探讨2大小序列的可能性。 对于size = 1 => [-1]，[1] 对于size = 2，将-1添加到之前的所有可能性中，并将1添加到以前的可能性中。所以，我们会有 [-1，-1] [1，-1] [-1,1] [1,1]
• 同样，每种新的可能性取决于它的子集可能性，并且为每种可能性添加curr元素产生当前的新可能性/序列。

Answer 3

在@BretC's answer上略微改进，我们可以避免创建尽可能多的BigIntegers并进行位掩码操作：

import java.math.BigInteger;
import java.util.Arrays;

public class AllSeq {

    public static void main(String[] args) {
        // Get the number of elements from args or default to 4
        int n = args.length > 0 ? Integer.parseInt(args[0]) : 4;

        // Work out total number of combinations (2^n)
        BigInteger bitValue = BigInteger.valueOf(2).pow(n);
        int firstOne = n-1;

        // For each combination...
        while(firstOne >= 0) {
            bitValue = bitValue.subtract(BigInteger.ONE);
            firstOne = bitValue.getLowestSetBit()

            // Initialise an array with 'n' elements all set to -1
            int[] resultForThisCombination = new int[n];
            Arrays.fill(resultForThisCombination, -1);

            if(firstOne >= 0) {
                // We now go through each bit in the combination...
                for(int bit = firstOne; bit < n; bit++) {
                // If the bit is set, set array element to 1 else set it to -1...
                    if(bitValue.testBit(bit)) {
                        resultForThisCombination[bit] = 1;
                    }
                }
            }

            // Print result / do whatever with it
            System.out.println(Arrays.toString(resultForThisCombination));
        }
    }
}