LINUX.ORG.RU

Найти все комбинации матрицы (java)

 , ,


1

1

Есть 2х мерный массив объектов (матрица)

MyClass[][] array = new MyClass[n][n];
массив может быть заполнен элементами 0 или 1. Значения устанавливает отдельная функция класса MyClass. По умолчанию массив заполнен нулями.

Надо пройти ВСЕ возможные комбинации нулей и единиц в этом массиве. Лупами, без использования рекурсии. Каждую получившуюся комбинацию нужно иметь возможноть сравнить с имеющейся (здесь не дано). Знаю, что количество полученных комбинаций очень велико, 2^(n*n), но все же.

Язык java.



Последнее исправление: buldoser11 (всего исправлений: 1)

Ответ на: комментарий от buldoser11

1. представь себе эту матрицу как одномерный массив битов
2. представь, что происходит когда к двоичному числу (массиву битов) добавляется 1
3. напиши цикл от 00000 до 11111 с отображением этого двоичного числа обратно в матрицу
...
n. PROFIT

maloi ★★★★★
()
Последнее исправление: maloi (всего исправлений: 1)
Ответ на: комментарий от buldoser11

Делаешь цикл i = от 0 до [ (2 в степени n*n) - 1 ].

В теле цикла преобразуешь число i в двоичную систему счисления (набор битов). И заполняешь полученными битами элементы двумерной матрицы - слева направо, сверху вниз.

Deleted
()
Последнее исправление: Deleted (всего исправлений: 2)

Вот и перечисляй от 0 до 2^(n*n)-1. А полученное число мапь на свою матрицу. Язык пофигу.

blexey ★★★★★
()

Представляем матрицу как одномерный массив бит отображением
(i, j) -> i * n + j
Изначально она забита нулями, 2^(n*n) раз делаем инкремент числу, которое эта последовательность бит представляет

BlackHawk
()
Ответ на: комментарий от buldoser11

3x3 это 9 бит. Помещается в целое. Младшие 3 бита - первая строка, следующие три бита - вторая строка... Просто инкрементить число.

Какие ограничения накладываются на n?

ziemin ★★
()

for (long counter = 0; counter < Long.MAX_VALUE; ++counter)

это идёт перебор всех комбинаций 63-х битов.

for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) arr[j] = (counter >> (i * n + j)) & 1

это идёт присваивание всех элементов матрицы.

В принципе всё. Работает для n <= 8, последний бит не перебирает, но в принципе это не важно, т.к. за разумное время всё равно не отработает и быстрее тоже вряд ли возможно.

А ещё лучше не вычитывать массив из битов counter-а, а использовать counter как есть. Сравнение - сравнение long-ов, моментальное.

Legioner ★★★★★
()

Ну ЙОПТЫТЬ. Какие хермутации. Представляешь массив двухмерный в виде одномерного, одномерный - как число в двоичной системе счисления и понимаешь, что надо его просто инкрементить, лол.

vsn
()

Мужики, вы чо неграмотные? Сказано же:

Язык java.

Какие нахрен массивы битов? Я считаю, для начала нужно создать абстрактную фабрику синглтонов.

harm
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.