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

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

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

Да
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
21.01.2022, 14:33
    #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:47
    #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, 19:11
    #40128569
Lemkoleg
Lemkoleg
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Динамически цикл для подчета возможных вариантов
faustgreen,
Спасибо большое
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
21.01.2022, 20:13
    #40128585
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Динамически цикл для подчета возможных вариантов
Еще один хороший пример в теку хвостовых рекурсий.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
22.01.2022, 12:32
    #40128669
Андрей Панфилов
Андрей Панфилов
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Динамически цикл для подчета возможных вариантов
mayton
Еще один хороший пример в теку хвостовых рекурсий.


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


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


Ой, прошу прощения. оно не не число сочетаний считает, а решает задачу в лоб
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
22.01.2022, 13:46
    #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, 19:05
    #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:20
    #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
| Ответить | Цитировать | Написать  
23.01.2022, 15:15
    #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, 17:22
    #40128831
faustgreen
faustgreen
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Динамически цикл для подчета возможных вариантов
Андрей Панфилов, можешь пояснить почему во втором варианте мы делим на "k",
это наблюдение или математикой выводилось?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
23.01.2022, 21:36
    #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, 22:50
    #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
| Ответить | Цитировать | Написать  
24.01.2022, 05:15
    #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
| Ответить | Цитировать | Написать  
30.01.2022, 19:08
    #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
| Ответить | Цитировать | Написать  
Форумы / Java [игнор отключен] [закрыт для гостей] / Динамически цикл для подчета возможных вариантов / 19 сообщений из 19, страница 1 из 1
Целевая тема:
Создать новую тему:
Автор:
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
созд. / загр.: 403ms
Закрыть
start [/forum/topic.php?fid=59&mobile=1&tid=2120257]:
 0ms
get settings:
 9ms
get forum list:
 13ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 29ms
get topic data:
 11ms
get forum data:
 2ms
get page messages:
 56ms
get tp. blocked users:
 2ms
others: 275ms
total:  403ms
x
x
Закрыть


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