ReSQL.ru
     
powered by simpleCommunicator - 2.0.40     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Java [игнор отключен] [закрыт для гостей] / Динамически цикл для подчета возможных вариантов
19 сообщений из 19, страница 1 из 1
Динамически цикл для подчета возможных вариантов
    #40128235
Lemkoleg
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Lemkoleg
Участник
Доброго времени суток. Задача, скорее математическая. Возможно, кто подскажет. Есть байт-массив, размером N. Частично заполнен нулями, частично - единицами. Нужно написать код, который сможет подчитать все возможные варианты расположения существующих единиц в даном массиве.
...
Рейтинг: 0 / 0
20.01.2022, 21:26
| Ответить | Цитировать | Написать  
Динамически цикл для подчета возможных вариантов
    #40128239
Lemkoleg
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Lemkoleg
Участник
Или, математическая формула
...
Рейтинг: 0 / 0
20.01.2022, 21:50
| Ответить | Цитировать | Написать  
Динамически цикл для подчета возможных вариантов
    #40128248
Alexander A. Sak
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Alexander A. Sak
Участник
Дайте угадаю...

Число сочетаний из N по k, где N - размер массива, k - количество единиц в массиве?
...
Рейтинг: 0 / 0
20.01.2022, 22:30
| Ответить | Цитировать | Написать  
Динамически цикл для подчета возможных вариантов
    #40128257
Lemkoleg
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Lemkoleg
Участник
Alexander A. Sak
Дайте угадаю...

Число сочетаний из N по k, где N - размер массива, k - количество единиц в массиве?

Да
...
Рейтинг: 0 / 0
20.01.2022, 23:29
| Ответить | Цитировать | Написать  
Динамически цикл для подчета возможных вариантов
    #40128425
faustgreen
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
faustgreen
Участник
Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
package test;

public class CombinationCalculator {

	public static void main(String[] args) {
		int size = 500;
		int ones = 3;
		System.out.println(calculate(size, ones));
	}

	static long calculate(int size, int ones) {
		
		long result = 0;
		
		for (int i = ones; i > 0; i--) {
			if (size == ones) {
				result = result + 1;
				break;
			} else if (ones == 1) {
				result = size;
			} else {
				if (result == 0)
					result = 1l;
				
				result = result + calculate(size-i, ones - i + 1);
			}
		}

		return result;
	}
}


Size - размер массива;
Ones - количество единиц в массиве.
...
Рейтинг: 0 / 0
21.01.2022, 14:33
| Ответить | Цитировать | Написать  
Динамически цикл для подчета возможных вариантов
    #40128430
faustgreen
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
faustgreen
Участник
В пример выше можно добавить кэширование промежуточных результатов.
https://www.youtube.com/watch?v=GhiRlhPlJ9Q&ab_channel=%D0%A1%D0%B0%D1%88%D0%B0%D0%9B%D1%83%D0%BA%D0%B8%D0%BD
...
Рейтинг: 0 / 0
21.01.2022, 14:47
| Ответить | Цитировать | Написать  
Динамически цикл для подчета возможных вариантов
    #40128569
Lemkoleg
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Lemkoleg
Участник
faustgreen,
Спасибо большое
...
Рейтинг: 0 / 0
21.01.2022, 19:11
| Ответить | Цитировать | Написать  
Динамически цикл для подчета возможных вариантов
    #40128585
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Еще один хороший пример в теку хвостовых рекурсий.
...
Рейтинг: 0 / 0
21.01.2022, 20:13
| Ответить | Цитировать | Написать  
Динамически цикл для подчета возможных вариантов
    #40128669
Андрей Панфилов
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Андрей Панфилов
Участник
mayton
Еще один хороший пример в теку хвостовых рекурсий.


ну во-первых это никакая не хвостовая рекурсия, во-вторых оно непонятно как написано да и к тому же в несколько раз медленнее классической рекурсивной формулы: (k/n) = (k-1/n-1) + (k/n-1)
...
Рейтинг: 0 / 0
22.01.2022, 12:32
| Ответить | Цитировать | Написать  
Динамически цикл для подчета возможных вариантов
    #40128680
Андрей Панфилов
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Андрей Панфилов
Участник
Андрей Панфилов
mayton
Еще один хороший пример в теку хвостовых рекурсий.


ну во-первых это никакая не хвостовая рекурсия, во-вторых оно непонятно как написано да и к тому же в несколько раз медленнее классической рекурсивной формулы: (k/n) = (k-1/n-1) + (k/n-1)


Ой, прошу прощения. оно не не число сочетаний считает, а решает задачу в лоб
...
Рейтинг: 0 / 0
22.01.2022, 13:34
| Ответить | Цитировать | Написать  
Динамически цикл для подчета возможных вариантов
    #40128683
Roman Osipov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Roman Osipov
Гость
Lemkoleg
Alexander A. Sak
Дайте угадаю...

Число сочетаний из N по k, где N - размер массива, k - количество единиц в массиве?

Да



Формула для перестановок с повторениями:

Pn(k, N - k) = N! / (k! * (N-k)!)
...
Рейтинг: 0 / 0
22.01.2022, 13:46
| Ответить | Цитировать | Написать  
Динамически цикл для подчета возможных вариантов
    #40128704
faustgreen
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
faustgreen
Участник
Андрей Панфилов
во-вторых оно непонятно как написано
Решалось на бумажке, без математики.

По условию задачи:
- Размер массива - size .
- Количество единиц в массиве - ones .

Возмем рандомный массив с единицами: [ 0010101 ]
1) Так как порядок следования едениц в массиве не имеет значения, перепишем массив в виде
[ 1110000 ]

2) Разобъем полученный масиив на две части
A[ 111 ] B[ 0000 ].

3) Теперь заставим крайний левый ноль "дрейфовать" влево,
каждый раз вытесняя единичку из левой части в правую
[ 111 ] [ 0000 ]
[ 110 ] [ 1000 ]
[ 10 ] [ 11000 ]
[ 0 ] [ 111000 ]

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

Количество комбинаций расположения единиц в массиве [1110000 ]=
все возможные комбинации расположения едениц в массиве [ 0000 ] с добавлением [ 111 ] в начале
+ все возможные комбинации расположения едениц в массиве [ 1000 ] с добавлением [ 110 ] в начале
+ все возможные комбинации расположения едениц в массиве [ 11000 ] с добавлением [ 10 ] в начале
+ все возможные комбинации расположения едениц в массиве [ 111000 ] с добавлением [ 0 ] в начале

5) Для сложения этих строк в коде выше используется цикл for
Код: java
1.
for (int i = ones; i > 0; i--) {}



6) Для вычисление количества комбинцаций в правой части каждой строки берем значения:
a) 1, если размер массива равен количеству единиц в нем, например [1111]
(только одна возможная комбинация).
b) size - размер массива, если количество единиц в массиве = 1, например [0000100]
с) вызываем ту же функцию расчета комбинаций, но с другими значениями size и ones,
например для [11000].

7) Так как "лесенка" начинается со второй строки, то первую строку мы вычисляем сами:
Код: java
1.
2.
if (result == 0)
   result = 1l;


Значение равно единице, так как может существовать только 1 комбинация начинающаяся с [111] с всевозможным количество перестановк единиц в масииве[0000]
...
Рейтинг: 0 / 0
22.01.2022, 19:05
| Ответить | Цитировать | Написать  
Динамически цикл для подчета возможных вариантов
    #40128706
faustgreen
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
faustgreen
Участник
Андрей Панфилов
да и к тому же в несколько раз медленнее классической рекурсивной формулы: (k/n) = (k-1/n-1) + (k/n-1)

Если добавить кэш, будет намного быстрее
Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
package test;

public class CombinationCalculator {
	
	static long[][] cash;
	
	public static void main(String[] args) {
		int size = 50;
		int ones = 25;
		
		cash = new long[size][ones];
		
		System.out.println(calculate(size, ones));
	}

	static long calculate(int size, int ones) {

		long result = 0;
		
		for (int i = ones; i > 0; i--) {
			if (size == ones) {
				result = 1;
				break;
			} else if (ones == 1) {
				result = size;
			} else {
				if (result == 0)
					result = 1l;
				
				long cashedValue = cash[size-1][ones-1];
				if (cashedValue > 0) {
					result = cashedValue;
				} else {
					result = result + calculate(size-i, ones - i + 1);
				}	
			}
		}
		
		cash[size-1][ones-1] = result;
		
		return result;
	}
}
...
Рейтинг: 0 / 0
22.01.2022, 19:20
| Ответить | Цитировать | Написать  
Динамически цикл для подчета возможных вариантов
    #40128803
Андрей Панфилов
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Андрей Панфилов
Участник
faustgreen

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

Количество комбинаций расположения единиц в массиве [1110000 ]=
все возможные комбинации расположения едениц в массиве [ 0000 ] с добавлением [ 111 ] в начале
+ все возможные комбинации расположения едениц в массиве [ 1000 ] с добавлением [ 110 ] в начале
+ все возможные комбинации расположения едениц в массиве [ 11000 ] с добавлением [ 10 ] в начале
+ все возможные комбинации расположения едениц в массиве [ 111000 ] с добавлением [ 0 ] в начале

ну вот здесь оно как минимум три раза одно и то же считает.

Есть две вполне очевидных стратегии:
1. если есть K единиц для массива длиной N, то:
- если мы в позицию 0 ставим 0, то еще нужно разместить K единиц в массиве длиной N-1
- если мы в позицию 0 ставим 1, то еще нужно разместить K-1 единиц в массиве длиной N-1
т.е. (k/n) = (k/n-1) + (k-1/n-1)
2. с хвоста, как любит mayton: допустим что у нас есть все перестановки K-1 единиц в массиве длиной N-1, чтобы получить перестановки K единиц в массиве длиной N, нужно единицу расставить во все возможные позиции уже имеющихся перестановок (т.е умножить на N) и избавиться от дублей (поделить на K), т.е. (k/n) = (k-1/n-1) * n / k
...
Рейтинг: 0 / 0
23.01.2022, 15:15
| Ответить | Цитировать | Написать  
Динамически цикл для подчета возможных вариантов
    #40128831
faustgreen
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
faustgreen
Участник
Андрей Панфилов, можешь пояснить почему во втором варианте мы делим на "k",
это наблюдение или математикой выводилось?
...
Рейтинг: 0 / 0
23.01.2022, 17:22
| Ответить | Цитировать | Написать  
Динамически цикл для подчета возможных вариантов
    #40128864
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Roman Osipov
Lemkoleg
пропущено...

Да



Формула для перестановок с повторениями:

Pn(k, N - k) = N! / (k! * (N-k)!)

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

Варианты.

1) Треугольник паскаля. Требует чуть дополнительной памяти.

2) Если частично сократить N! и k! по правилу сокращения дробей то выходит что-то вроде.

С(2,5) = 5! / 2!(5-2)! = 4 * 5 / 1 * 2
...
Рейтинг: 0 / 0
23.01.2022, 21:36
| Ответить | Цитировать | Написать  
Динамически цикл для подчета возможных вариантов
    #40128879
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Как вариант

Код: java
1.
2.
3.
4.
5.
  def C(n: Int, m: Int): Int = {
    @tailrec
    def C2(n: Int, d: Int, np: Int, dp: Int): Int = if (d >= 1) C2(n - 1, d - 1, np * n, dp * d) else np / dp
    C2(m, n, 1, 1)
  }



(m,n)C(m,n)C(1,1) 1C(1,2) 2C(1,3) 3C(1,4) 4C(1,5) 5C(1,6) 6C(1,7) 7C(2,2) 1C(2,3) 3C(2,4) 6C(2,5) 10C(2,6) 15C(2,7) 21C(3,3) 1C(3,4) 4C(3,5) 10C(3,6) 20C(3,7) 35C(4,4) 1C(4,5) 5C(4,6) 15C(4,7) 35C(5,5) 1C(5,6) 6C(5,7) 21C(6,6) 1C(6,7) 7C(7,7) 1
...
Рейтинг: 0 / 0
23.01.2022, 22:50
| Ответить | Цитировать | Написать  
Динамически цикл для подчета возможных вариантов
    #40128915
Андрей Панфилов
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Андрей Панфилов
Участник
faustgreen
Андрей Панфилов, можешь пояснить почему во втором варианте мы делим на "k",
это наблюдение или математикой выводилось?


ну во-первых (k/n) = (k-1/n-1) * n / k - это просто результат формулы n! / k! * (n-k)! = n(n-1)! / k(k-1)! * (n-1 - (k - 1))!, однако если не прибегать к формулам (т.е. решать задачу исключительно комбинаторикойпрограммированием, а не математикой), то можно рассуждать примерно так:
- когда мы добавляем единицу в уже существующие перестановки (k-1/n-1), мы ее какбы "маркируем", т.е. мы знаем что вот она наша последняя добавленная единица и количество перестановок у нас получается n * (k-1/n-1)
- аналогичный набор у нас бы получился если бы мы в перестановках (k/n) маркировали бы одну единицу, в этом случае количество перестановок у нас было бы k * (k/n)
...
Рейтинг: 0 / 0
24.01.2022, 05:15
| Ответить | Цитировать | Написать  
Динамически цикл для подчета возможных вариантов
    #40130608
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Боллее строгий вариант на Haskell. Допускаем только сочетания меньшего количества элементов из большего.

Код: python
1.
2.
3.
4.
5.
6.
7.
8.
9.
{-- mayton, sql.ru : Jan-24. 2022  --}

comb :: Int -> Int -> Maybe Int
comb n m
   | n <= m = Just $ comb' m n 1 1
   | otherwise = Nothing
      where
        comb' :: Int -> Int -> Int -> Int -> Int
        comb' num den num_prod den_prod = if den >= 1 then comb' (num - 1) (den - 1) (num * num_prod) (den * den_prod) else num_prod `div` den_prod



Тоесть лотерея 5 из 36 без учета порядка шариков дала-бы

Код: plsql
1.
2.
Prelude> comb 5 36
Just 376992



Наоборот - логически нельзя ибо безсмыслица. Сочетания 45 шаров из 6 возможных взять нельзя.

Код: java
1.
2.
Prelude> comb 45 6
Nothing
...
Рейтинг: 0 / 0
30.01.2022, 19:08
| Ответить | Цитировать | Написать  
19 сообщений из 19, страница 1 из 1
Форумы / Java [игнор отключен] [закрыт для гостей] / Динамически цикл для подчета возможных вариантов
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
NoSQL.ru             Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=59&gotonew=1&tid=2120257]:
 0ms
get settings:
 11ms
get forum list:
 15ms
check forum access:
 4ms
check topic access:
 4ms
track hit:
 38ms
get topic data:
 12ms
get first new msg:
 8ms
get forum data:
 3ms
get page messages:
 61ms
get tp. blocked users:
 2ms
others: 282ms
total:  440ms
созд. / загр.: 440ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]