logic - 编写代码来枚举给定数量元素的所有可能排列

Question

这个问题并不是关于代码的语法，而是实际上我应该如何创建一个方法。

当程序启动时，您输入组合中开关数量的数字，每个组合由可以具有开/关值的开关数量组成。然后程序会遍历所有不同的组合并打印它可能得出的金额。

我需要帮助的部分是 nextCombination 方法。截至目前，我正在使用随机生成的组合，这会导致较大数字的输出不准确且不一致。我想知道如何创建一个系统方法来执行此操作。

这是我输入“2”的示例:

> Enter the length of the combination: 2
> FT
> FF
> TF
> TT
> Number of combinations: 4

这是组合类:

public class Combination {

    private int number;

    private boolean[] values;

    public Combination(int number) {
        this.number = number;
        values = new boolean[number];
    }

    public Combination(boolean[] values) {
        this.number = values.length;
        this.values = values;
    }

    public void setValue(int i, boolean value) {
        values[i] = value;
    }

    @Override
    public boolean equals(Object o) {
        if (o instanceof Combination) {
            if (((Combination) o).number != number) {
                return false;
            }
            for (int i = 0; i < ((Combination) o).number; i++) {
                if (values[i] != ((Combination) o).values[i]) {
                    return false;
                }
            }
            return true;
        }
        return super.equals(o);
    }

    @Override
    public String toString() {
        String s = "";
        for (boolean b : values) {
            s = s + (b ? "T" : "F");
        }
        return s;
    }

}

这是主类:

import java.util.ArrayList;
import java.util.Scanner;

public class Main {

    private final static int MAXIMUM_ATTEMPTS = 500;

    private static int attempts;

    private static int number;

    private static ArrayList<Combination> cache = new ArrayList<Combination>();

    private static Scanner myScanner = new Scanner(System.in);

    public static void main(String... s) {
        System.out.print("Enter the length of the combination: ");
        number = myScanner.nextInt();
        Combination combination = nextCombination();
        while (combination != null) {
            if (!hasCombinationBeenUsed(combination)) {
                cache.add(combination);
                System.out.println(combination);
            }
            combination = nextCombination();
        }
        System.out.println("Number of combinations: " + Integer.toString(cache.size()));
    }

    private static Combination nextCombination() {
        boolean[] values = new boolean[number];
        for (int i = 0; i < number; i++) {
            values[(int) (Math.random() * number)] = ((int) (Math.random() * (2))) == 1;
        }
        Combination combo = new Combination(values);
        if (!hasCombinationBeenUsed(combo)) {
            return combo;
        } else if (attempts < MAXIMUM_ATTEMPTS) {
            attempts++;
            return nextCombination();
        } else {
            return null;
        }
    }

    private static boolean hasCombinationBeenUsed(Combination combo) {
        for (Combination c : cache) {
            if (c.equals(combo)) {
                return true;
            }
        }
        return false;
    }

}

对此的任何帮助都是值得赞赏的，如果您能让我的代码更好/更短/更高效，那么我也希望如此。谢谢:)

编辑:我才 15 岁，所以我没有上过学，所以不要太严厉

Answer 1

看起来您已经准备好学习二进制算术了!将组合视为由 0 和 1 组成的序列，代表一个二进制数。 TFF 代表 4，TFT 代表 5，依此类推。然后想出下一个组合就相当于增加值 - 就是这么简单!

借助用 Java、C、C++、C# 等实现的二进制运算，您可以得到以下代码:

int size = 5;
for (int mask = 0 ; mask != (1 << size) ; mask++) {
    for (int i = size-1 ; i >= 0 ; i--) {
        System.out.print((mask & (1 << i)) == 0 ? 'F' : 'T');
    }
    System.out.println();
}

阅读page or two on bit operations ，然后使用此代码 at ideone看看它是如何工作的。我鼓励您与小数世界做一些类比，您将学到很多关于数字系统的知识!