Знаю, что в зависимости от длины числа получается
2^(N-1) вариантов, где
N - длина числа.
Например число 1234: (тогда 2^(4)=
8)
- [1234]
- [1] [2] [3] [4]
- [1] [2] [34]
- [1] [23] [4]
- [1] [234]
- [12] [3] [4]
- [12] [34]
- [123] [4]
Рекурсия не подойдет, наверное, потому что мне нужно сохранять эти варианты.
младшаяЦифра = число % 10;
число = число / 10;
повторять, пока число не станет 0.
— то есть находим остаток от деления числа на 10. Например, число 365: после первой операции имеем младшаяЦифра = 365%10 = 5;
второй строчкой «укорачиваем» наше число, чтобы дальше получить следующую с конца цифру (деление целочисленное):
число = 365/10 = 36.
Повторив шаги, получим по порядку далее цифру 6 и цифру 3. после последнего деления 3/10 = 0, выходим из цикла.
Как оформить это в код, сохраняя цифры и как исправить их порядок для ответа, оставляю как упражнение для автора =)
берем числа от 0 до 2^(N — 1) и рассматриваем их двоичное представление: для N = 4
000
001
010
011
100
101
110
111
Далее «разбираем» эти числа по битам (см. побитовые операции в Java) и в случае 1 «склеиваем» соседние цифры, а в случае 0 разделяем. Реализовать можно по-разному: либо сперва разлепить все цифры как в моем первом ответе и склеивать по необходимости, либо в каждом случае разлеплять число только в нужных местах, на которые указывает бит 0 в двоичном «шаблоне», полученном выше.
000 -> 1 2 3 4
001 -> 1 2 34
010 -> 1 23 4
011 -> 1 234
и так далее
По реализации проще будет пользоваться строковым представлением чисел, а по производительности, скорее всего, лучше поиграться с арифметикой.
Число всех перестановок порядка n равно числу размещений из n по n, то есть факториалу
соответственно
из числа 1234, можно составить 24 варианта
Заметил закономерность. буду рыть в этом направлении)) Помогите, просто устал уже. Я уже этих алгоритмов нарешался за 3 дня))
1 2 3 4
1 вариант: 1, 2, 3, 4
берем 1
2 вариант 1 234
3 вариант 12 34
4 вариант 123 4
берем 2
5 вариант 1 2 34
6 вариант 1 23 4
берем 3
7 вариант 12 3 4
Вот мой говнокод)))) его можно причесать, но не суть. я проверяю строчную длину двоичного представления и если меньше 2^(N-1)-1 то добавляю лидирующие нули. Думаю все должно быть на много проще.
получается:
0000000
0000001
0000010
0000011
0000100
0000101
0000110
0000111
0001000
0001001
и т.д.
Вот пример:
Вывод программы:
0000000001111101
Поясню что происходит в условии: (1<<i) — это единица, сдвинутая на i позиций влево в двоичном представлении числа.
& (заметьте, не &&) — это побитовое сравнение чисел, побитовый AND (если на одинаковых позициях у обоих чисел 1, то в результате на этой позиции тоже 1. Если хоть в одном 0, в результате тоже 0). Мы сравниваем побитово наше число с числом, где все нули и одна единица на нужной позиции. Так мы проверяем, есть ли в нашем числе на данной позиции единица или ноль
То есть 0100010 & 0100000 = 0100000
а 0100010 & 0010000 = 00000000
Таким образом, сравнивая результат с нулем, можно решить, что делать с соседними цифрами нашего числа: клеить или разделять.
i = 2^(N-1)-1
Массив points содержит индексы после которых нужно резать число в строчном выражении или опять же в массиве.
не нужна.
Она портит число, и даже если бы не портила, получилось бы, что вырыл яму и снова закопал )
А фактически получается, что из числа 12 в десятичной форма получаешь строку «1100» и его переводишь в число 1100 опять в десятичной форме. Это неверно.
Можно цикл прогнать и по исходному числу i — смотри в моем примере: я число 125 ни во что не преобразовывал. Оно в компе и так в памяти хранится в виде набора битов — в двоичном виде.