Написание кода для перечисления всех возможных перестановок заданного числа элементов

Question

Этот вопрос касается не столько синтаксиса кода, сколько фактического способа создания метода.

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

Часть, в которой мне нужна помощь, - следующий метод объединения. На данный момент я использую случайное генерирование комбинации, что приводит к неточным и несогласованным выводам для больших чисел. Я хотел бы знать, как бы я хотел создать систематический метод для этого.

Heres пример мне ввод '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

Похоже, вы готовы узнать о бинарных арифметике! Подумайте о комбинации как последовательности нулей и единиц, представляющих двоичное число. 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, чтобы увидеть, как это работает. Я рекомендую вам сделать некоторые параллели с миром десятичных знаков, вы узнаете много о системных системах в целом!