Самый быстрый способ генерировать все двоичные строки размером n в логический массив? - PullRequest
Новая
       30

Самый быстрый способ генерировать все двоичные строки размером n в логический массив?

9 голосов
/ 04 декабря 2011

Например, если бы я хотел все двоичные строки длины 3, я мог бы просто объявить их так: 

boolean[] str1 = {0,0,0};
boolean[] str2 = {0,0,1};
boolean[] str3 = {0,1,0};
boolean[] str4 = {0,1,1};
boolean[] str5 = {1,0,0};
boolean[] str6 = {1,0,1};
boolean[] str7 = {1,1,0};
boolean[] str8 = {1,1,1};

Как наиболее эффективно сгенерировать все возможные двоичные строки длины N в логический массив ?

Мне не обязательно нужен самый эффективный метод, достаточно эффективный и простой для многопоточности.

РЕДАКТИРОВАТЬ: я должен отметить, что я буду хранить их все в ArrayList, если это имеет значение.

Ответы [ 6 ]

6 голосов
/ 04 декабря 2011

Вот некоторый код для генерации таблицы истинности ... (работает только для 32 бит из-за ограничений размера массива (вы можете изменить переменную размера на любую и сохранить логические значения как 1/0, если хотите): 

int size = 3;
    int numRows = (int)Math.pow(2, size);
    boolean[][] bools = new boolean[numRows][size];
    for(int i = 0;i<bools.length;i++)
    {
        for(int j = 0; j < bools[i].length; j++)
        {
            int val = bools.length * j + i;
            int ret = (1 & (val >>> j));
            bools[i][j] = ret != 0;
            System.out.print(bools[i][j] + "\t");
        }
        System.out.println();
    }
4 голосов
/ 25 октября 2012

Пример: если вам нужна длина 4, то у вас должно быть 2 ^ 4 = 16 различных массивов.

Вы можете использовать этот простой код Java для генерации всех массивов: 

for (int i=0; i < (Math.pow(2,4)); i++) {
        System.out.println(Integer.toBinaryString(i));
}

Вывод этого:

0 1 10 11 100 101 110 111 1000 1001 1010 1011 1100 1101 1110 1111

3 голосов
/ 04 декабря 2011

Если вам не нужны все перестановки сразу, разумно сделать так: заранее не выделить памяти и просто написать алгоритм, который вычисляет strX хочешь, на лету.

Преимущества этого:

  • Вы можете обрабатывать произвольно большое количество перестановок без необходимости выделять все перестановки
  • Поскольку алгоритм ничего не хранит, он дружественный к потоку
  • Вы платите только за те строки, которые хотите. Например, если n = 1000, но вам нужно всего лишь несколько перестановок, это будет намного быстрее и потребует небольшую долю памяти (стоит только одна строка)

Для начала интерфейс алгоритма может выглядеть примерно так:

логическое значение [] getRow (int rowNumber, int nItems)

Таким образом, вы бы позвонили getRow(5,3), чтобы получить str5, возвращенную из функции. Я оставляю это на ваше усмотрение, чтобы реализовать детали (это не сложно).

1 голос
/ 22 марта 2017

Вот как я это сделал на Java 

public class NbitsStrings {
    int[] arrA;
    public static void main(String[] args) throws java.lang.Exception {
        Scanner input = new Scanner(System.in); //Input the Number Of bits you want.
        int n = input.nextInt();
        NbitsStrings i = new NbitsStrings(n);
        i.nBits(n);
    }
    public NbitsStrings(int n) {
        arrA = new int[n];
    }
    public void nBits(int n) {
        if (n <= 0) {
            StringBuilder builder = new StringBuilder();
            for (int value : arrA) {
                builder.append(value);
            }
            String text = builder.toString();
            System.out.println(text);
        } else {
            arrA[n - 1] = 0;
            nBits(n - 1);
            arrA[n - 1] = 1;
            nBits(n - 1);
        }
    }
}
1 голос
/ 04 декабря 2011

Реализовано это в функции - 

static public ArrayList<boolean[]> getBoolArr(int length) {
        int numOptions = 1 << length;
        ArrayList<boolean[]> finalArray = new ArrayList<boolean[]>();
        for(int o=0;o<numOptions;o++) {
            boolean[] newArr = new boolean[length];
            for(int l=0;l<length;l++) {
                int val = ( 1<<l ) & o;
                newArr[l] = val>0;
            }
            finalArray.add(newArr);
        }
        return finalArray;
    }

пример использования- 

ArrayList<boolean[]> res = getBoolArr(2); //2 is your length, change it however you want.
0 голосов
/ 04 марта 2017

javascript реализация, относящаяся к дубликату Вопрос https://stackoverflow.com/questions/42591231/calculate-all-possible-combinations-of-n-off-on-elements.

Как и для всех чисел, существует взаимосвязь между наборами чисел, где после распознавания шаблона можно использовать сложение для полученияотношения между наборами чисел по определенным индексам в наборе массивов. 

let [N, n1, n2, n3] = [0, 1, 9, 89];

let [res, max] = [Array(Array(3).fill(N)), Math.pow(2, 3)];

for (let i = 1, curr; i < max; i++) {

  if ([1, 3, 5, 7].some(n => n === i)) {
    N += n1;
  }

  if ([2, 6].some(n => n === i)) {
    N += n2;
  }

  if (i === max / 2) {
    N += n3;
  }

  curr = Array.from(String(N), n => +n);

  if (N < 100) {
    while (curr.length < 3) {
      curr.unshift(n1 - 1);
    }
  }

  res.push(curr);

}

console.log(res);
...