ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / алгоритм перебора всех возможных значений
25 сообщений из 27, страница 1 из 2
  1  все
алгоритм перебора всех возможных значений
    #36490423
pavlickm
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
pavlickm
Гость
сложно описать задачу, напишу примеры
дано число N=2
на выходе 12, 21.

дано число N=3
на выходе 123, 132, 213, 231, 312, 321.

дано число N=4
на выходе 1234, 1243, 1342, 1324, 1423, 1432, 2134, 2143, 2314, 2341, 2413, 2431, 3124, 3142, 3214, 3241, 3412, 3421, 4123, 4132, 4213, 4231, 4312, 4321.
...
Рейтинг: 0 / 0
26.02.2010, 15:40:33
| Ответить | Цитировать | Написать  
алгоритм перебора всех возможных значений
    #36490445
Mozok
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Mozok
Участник
pavlickm,

баян
...
Рейтинг: 0 / 0
26.02.2010, 15:49:37
| Ответить | Цитировать | Написать  
алгоритм перебора всех возможных значений
    #36490524
Фотография Пилотажный
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Пилотажный
Участник
А вообще алгоритмов известных (баянистых) и разных несколько. И не все типа построения порфириана.

Вот, например, метод вставками - как поэзия на Haskell

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
insert x [] = [[x]]
insert x (y:ys) = (x:y:ys) : map (\z -> y:z) (insert x ys)
permute [] = [[]]
permute (x:xs) = concat (map (insert x) (permute xs))

Main> permute [ 1 , 2 , 3 , 4 ]
[[ 1 , 2 , 3 , 4 ],[ 2 , 1 , 3 , 4 ],[ 2 , 3 , 1 , 4 ],[ 2 , 3 , 4 , 1 ],[ 1 , 3 , 2 , 4 ],[ 3 , 1 , 2 , 4 ],[ 3 , 2 , 1 , 4 ],[ 3 , 2 , 4 , 1 ],[ 1 , 3 , 4 , 2 ],[ 3 , 1 , 4 , 2 ],[ 3 , 4 , 1 , 2 ],[ 3 , 4 , 2 , 1 ],[ 1 , 2 , 4 , 3 ],[ 2 , 1 , 4 , 3 ],[ 2 , 4 , 1 , 3 ],[ 2 , 4 , 3 , 1 ],[ 1 , 4 , 2 , 3 ],[ 4 , 1 , 2 , 3 ],[ 4 , 2 , 1 , 3 ],[ 4 , 2 , 3 , 1 ],[ 1 , 4 , 3 , 2 ],[ 4 , 1 , 3 , 2 ],[ 4 , 3 , 1 , 2 ],[ 4 , 3 , 2 , 1 ]]
...
Рейтинг: 0 / 0
26.02.2010, 16:26:00
| Ответить | Цитировать | Написать  
алгоритм перебора всех возможных значений
    #36490541
pavlickm
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
pavlickm
Гость
Пилотажный, Mozok,
да это всё примеры на конкретных языках, мне алгоритм нужен, я ж не буду изучать хаскель что бы понять как он это делат, так же мне не очень охота лезть в исходники algorithm, что бы реализовать это у себя
...
Рейтинг: 0 / 0
26.02.2010, 16:32:33
| Ответить | Цитировать | Написать  
алгоритм перебора всех возможных значений
    #36490582
Фотография Пилотажный
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Пилотажный
Участник
pavlickm,
метод со вставками
с конца
1 - список пуст
2 - список 1 - вставки 21, 12
3 - два списка 21, 12 - вставки в первый 321, 231, 213, во второй 312, 132, 123
и т.д.
...
Рейтинг: 0 / 0
26.02.2010, 16:49:04
| Ответить | Цитировать | Написать  
алгоритм перебора всех возможных значений
    #36491243
Vowk
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Vowk
Участник
Можно рассуждать так:
1. Выбираем на 1-е место любой элемент из N возможных по порядку от 1 до N.
2. На 2-е место выбираем любой элемент из (N-1) возможных (кроме того, что уже выбран на 1-е место).
3. На 3-е место выбираем любой элемент из (N-2) возможных (кроме двух тех, что уже выбраны на 1-е и 2-е место).
....
N-1. На (N-1)-е место выбираем один из 2-х оставшихся не выбранными элемента.
N. На N-е место выбора нет - туда попадает последний оставшийся невыбранным элемент.
...
Рейтинг: 0 / 0
26.02.2010, 22:37:04
| Ответить | Цитировать | Написать  
алгоритм перебора всех возможных значений
    #36491284
AIS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AIS
Участник
pavlickm ,
чтобы делать замечания, надо хотя бы немного почитать теорию по матиматике и программированию.
...
Рейтинг: 0 / 0
26.02.2010, 23:29:31
| Ответить | Цитировать | Написать  
алгоритм перебора всех возможных значений
    #36491553
Vowk
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Vowk
Участник
Вот примерная реализация изложенного мною нерекурсивного алгоритма для EXCEL.
Здеcь LEV - индекс элемента в перестановке
Код: plaintext
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.
Sub TEST()
Const N =  5  
Dim ar(N) As Integer, lev As Integer, nrow As Integer
Cells.Clear
lev =  1 : ar(lev) =  1 
 1 :
For i =  1  To lev -  1      'проверяем, не был ли выбран элемент ранее
   If ar(i) = ar(lev) Then  ' не месте (i) был выбран ранее, следует взять другой
      If ar(lev) < N Then
         ar(lev) = ar(lev) +  1 
         GoTo  1  'повторяем попытку для другого значения
      Else ' выбор на месте LEV уже исчерпан
         GoTo  2  'идем на уменьшение LEV
      End If
   End If
Next
' ar(lev) наконец-то выбран
If lev < N Then 'увеличиваем LEV и повторяем поиск невыбранного элемента
   lev = lev + 1
   ar(lev) = 1
   GoTo 1
Else   ' выбраны все элементы, можно печатать вариант
   s = ""
   For i =  1  To N
      s = s & ar(i)
   Next
   nrow = nrow +  1 
   Cells(nrow,  1 ) = s
 2 :
   lev = lev -  1   ' отступаем назад, чтобы выбрать другой элемент
   If lev < 1 Then End ' LEV дальше уменьшать некуда  - все варианты исчерпаны
   If ar(lev) < N Then ' такая возможность еще имеется
      ar(lev) = ar(lev) + 1
      GoTo 1
   Else ' на уровне LEV такой возможности уже нет
      GoTo  2  ' идем на дальнейшее уменьшение LEV
   End If
End If
End Sub
...
Рейтинг: 0 / 0
27.02.2010, 09:29:07
| Ответить | Цитировать | Написать  
алгоритм перебора всех возможных значений
    #36491570
Vowk
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Vowk
Участник
Немного исправил (end if не там поставил, хотя на работе не отражается). Комменты второй раз не перепечатываю, уж извините:
Код: plaintext
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.
Sub TEST()
Const N =  5 
Dim ar(N) As Integer, lev As Integer, nrow As Integer
Cells.Clear
lev =  1 : ar(lev) =  1 
 1 :
For i =  1  To lev -  1  'ïðîâåðÿåì, íå áûë ëè âûáðàí ýëåìåíò ðàíåå
   If ar(i) = ar(lev) Then  ' íà ìåñòå (i) áûë âûáðàí ðàíåå, ñëåäóåò âçÿòü äðóãîå ÷èñëî
      If ar(lev) < N Then
         ar(lev) = ar(lev) +  1 
         GoTo  1  'ïîâòîðÿåì ïîïûòêó äëÿ äðóãîãî çíà÷åíèÿ
      Else ' âûáîð íà ìåñòå (lev) óæå èñ÷åðïàí
         GoTo  2  'èäåì íà óìåíüøåíèå LEV
      End If
   End If
Next
' ar(lev) íàêîíåö-òî âûáðàí
If lev < N Then 'óâåëè÷èâàåì lev è ïîâòîðÿåì ïîèñê íåâûáðàííîãî ýëåìåíòà
   lev = lev + 1
   ar(lev) = 1
   GoTo 1
Else   ' âûáðàíû âñå N ýëåìåíòîâ, ìîæíî ïå÷àòàòü ïåðåñòàíîâêó
   s = ""
   For i =  1  To N
      s = s & ar(i)
   Next
   nrow = nrow +  1 
   Cells(nrow,  1 ) = s
End If
 2 :
lev = lev -  1   ' îòñòóïàåì íàçàä, ÷òîáû âûáðàòü äðóãîé ýëåìåíò
If lev < 1 Then End
If ar(lev) < N Then ' òàêàÿ âîçìîæíîñòü åùå èìååòñÿ
   ar(lev) = ar(lev) +  1 
   GoTo  1 
Else ' íà óðîâíå LEV òàêîé âîçìîæíîñòè óæå íåò
    GoTo 2 ' èäåì íà äàëüíåéøåå óìåíüøåíèå LEV
End If
End Sub
...
Рейтинг: 0 / 0
27.02.2010, 09:36:42
| Ответить | Цитировать | Написать  
алгоритм перебора всех возможных значений
    #36491657
pavlickm
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
pavlickm
Гость
AIS pavlickm ,
чтобы делать замечания, надо хотя бы немного почитать теорию по матиматике и программированию.
мат е матике
что бы делать замечания на мои замечания, нужно хотя бы немного почитать теорию по орфографии русского языка. шучу =)
неохота мне читать, охота алгоритм.
...
Рейтинг: 0 / 0
27.02.2010, 10:29:10
| Ответить | Цитировать | Написать  
алгоритм перебора всех возможных значений
    #36491920
ShSerge
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ShSerge
Участник
По сабжу: а для n=2 такие, как 11 и 22 не годятся?
...
Рейтинг: 0 / 0
27.02.2010, 12:42:40
| Ответить | Цитировать | Написать  
алгоритм перебора всех возможных значений
    #36492297
pavlickm
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
pavlickm
Гость
ShSergeПо сабжу: а для n=2 такие, как 11 и 22 не годятся?
не годятся
...
Рейтинг: 0 / 0
27.02.2010, 15:21:07
| Ответить | Цитировать | Написать  
алгоритм перебора всех возможных значений
    #36492850
Памас
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Памас
Участник
javascript:

Код: plaintext
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.
44.
45.
46.
47.
48.
49.
50.
51.
<html><head>
<script type="text/javascript">
<!--
function e(A, n)
{
	var t, s0, s1, s2;
	var B = new Array();
	for (var i =  0 ; i < A.length; i++)
	{
		t = A[i];
		for (var j =  0 ; j <= t.length; j++)
		{
			s1 = t.substring( 0 , j)
			s2 = t.substring(j, t.length)
			s0 = s1 + n + s2;
			B[B.length] = s0;
		}
	}
	return B;
}

function f()
{
	if (document.getElementById("debbug").checked)
		debugger;
	var s = document.getElementById("Data").value;
	var N = s.split('');
	var A = new Array('');
	for (var i= 0 ; i < N.length; i++)
		A = e(A, N[i]);
	print(A);
}

function print(A)
{
	var s = "";
	for (var i= 0 ; i < A.length; i++)
		s += i + ") " + A[i] + "<br>";
	document.getElementById("Result").innerHTML = s;
}

// -->
</script>
</head>

<body>
	<input type="text" id="Data">
	<input type="button" value="run" onclick="f();">
	<input type="checkbox" id="debbug" checked title="for debugger">
	<br>
	<div id="Result" style="font-family:courier; HEIGHT: 500px; OVERFLOW: auto"></div>
</body></html>
...
Рейтинг: 0 / 0
27.02.2010, 22:32:31
| Ответить | Цитировать | Написать  
алгоритм перебора всех возможных значений
    #36492877
ShSerge
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ShSerge
Участник
Памас,

А чё Вы написали? Вы что, не читали, что ТС просит? Кстати, код-то ведь таки у Вас скопипащенный.
...
Рейтинг: 0 / 0
27.02.2010, 23:04:56
| Ответить | Цитировать | Написать  
алгоритм перебора всех возможных значений
    #36492912
Vowk
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Vowk
Участник
Ну да, теперь по этой программе попробуй-ка словесное опесание алгоритма дать - посложнее самой программы будет в несколько раз.
...
Рейтинг: 0 / 0
28.02.2010, 00:06:26
| Ответить | Цитировать | Написать  
алгоритм перебора всех возможных значений
    #36492915
Vowk
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Vowk
Участник
Что-то оно не работает. Скопировал в текстовый файл, переименовал в .html, и вот результаты (или я что-то не так делаю?)
...
Рейтинг: 0 / 0
28.02.2010, 00:13:06
| Ответить | Цитировать | Написать  
алгоритм перебора всех возможных значений
    #36493058
Памас
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Памас
Участник
ShSergeПамас,

А чё Вы написали? Вы что, не читали, что ТС просит? Кстати, код-то ведь таки у Вас скопипащенный.
1. да, похоже, я не понял условий
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
дано число N= 2 
на выходе  12 ,  21 .

дано число N= 3 
на выходе  123 ,  132 ,  213 ,  231 ,  312 ,  321 .

дано число N= 4 
на выходе
  1234 ,  1243 ,  1342 ,  1324 ,
  1423 ,  1432 ,  2134 ,  2143 ,
  2314 ,  2341 ,  2413 ,  2431 ,
  3124 ,  3142 ,  3214 ,  3241 ,
  3412 ,  3421 ,  4123 ,  4132 ,
  4213 ,  4231 ,  4312 ,  4321 .
- подумал что это перестановки
2. скопипащенный. - не правда , (возился сам, кстати, в это время по тв показывали китайских победителей соревнования программистов, и думалось мне не до них)
естественно такой подход наверняка известен и написан, а приступить к написаню подвигли суждения

Vowk
Можно рассуждать так:
1. Выбираем на 1-е место любой элемент из N возможных по порядку от 1 до N.
2. На 2-е место выбираем любой элемент из (N-1) возможных (кроме того, что уже выбран на 1-е место).
3. На 3-е место выбираем любой элемент из (N-2) возможных (кроме двух тех, что уже выбраны на 1-е и 2-е место).
....
N-1. На (N-1)-е место выбираем один из 2-х оставшихся не выбранными элемента.
N. На N-е место выбора нет - туда попадает последний оставшийся невыбранным элемент
- опять же см. п.1
...
Рейтинг: 0 / 0
28.02.2010, 10:34:28
| Ответить | Цитировать | Написать  
алгоритм перебора всех возможных значений
    #36493063
Памас
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Памас
Участник
VowkЧто-то оно не работает. Скопировал в текстовый файл, переименовал в .html, и вот результаты (или я что-то не так делаю?)
ввод:
для N=2 12
для N=3 ABC ...
...
Рейтинг: 0 / 0
28.02.2010, 10:37:58
| Ответить | Цитировать | Написать  
алгоритм перебора всех возможных значений
    #36493102
Vowk
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Vowk
Участник
Неправильно работает программа на Javascript (обратите внимание на две последние строки)
...
Рейтинг: 0 / 0
28.02.2010, 11:46:45
| Ответить | Цитировать | Написать  
алгоритм перебора всех возможных значений
    #36493105
Vowk
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Vowk
Участник
Не, таки правильно. Показалось, что одинаковые.
...
Рейтинг: 0 / 0
28.02.2010, 11:49:10
| Ответить | Цитировать | Написать  
алгоритм перебора всех возможных значений
    #36493302
AIS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AIS
Участник
Памас... подумал что это перестановки...
А что это тогда? И ваш код, по-моему, делает упорядочные перестановки.
VowkМожно рассуждать так:
1. Выбираем на 1-е место любой элемент из N возможных по порядку от 1 до N.
2. На 2-е место выбираем любой элемент из (N-1) возможных (кроме того, что уже выбран на 1-е место).
3. На 3-е место выбираем любой элемент из (N-2) возможных (кроме двух тех, что уже выбраны на 1-е и 2-е место).
....
N-1. На (N-1)-е место выбираем один из 2-х оставшихся не выбранными элемента.
N. На N-е место выбора нет - туда попадает последний оставшийся невыбранным элемент
У Вас, как я понимаю, неупорядочные перестановки. У меня как раз в этом направлении была задача. Я сначала сделал упорядочный массив перестановок, а потом случайным образом их в массиве попереставлял.
А как сделать то, что предлагаете Вы, но чтобы в циклах машина не зависла на долго и иметь весь массив вариантов? (т.е. сразу создать массив неупорядочных перестановок, а не через промежуточное действие)
...
Рейтинг: 0 / 0
28.02.2010, 14:59:34
| Ответить | Цитировать | Написать  
алгоритм перебора всех возможных значений
    #36493456
Памас
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Памас
Участник
AISПамас... подумал что это перестановки...
А что это тогда? И ваш код, по-моему, делает упорядочные перестановки.
-- не могу сказать, что такое (НЕ)упорядочные перестановки.
-- скорость круто падает, есно, при больших N

по сути предлагается найти все числа содержащие в своем представлении заданный
набор цифр(и только) .
тогда решение проще: пробежаться от 10^(N-1) до 10^N-1 и отобрать удовлетворяющие.
в качестве основания(10) надо рассматривать любое число, иначе при N>9 нет решения
...
Рейтинг: 0 / 0
28.02.2010, 18:00:15
| Ответить | Цитировать | Написать  
алгоритм перебора всех возможных значений
    #36493558
Фотография Пилотажный
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Пилотажный
Участник
ПамасAISПамас... подумал что это перестановки...
А что это тогда? И ваш код, по-моему, делает упорядочные перестановки.
-- не могу сказать, что такое (НЕ)упорядочные перестановки.
-- скорость круто падает, есно, при больших N

по сути предлагается найти все числа содержащие в своем представлении заданный
набор цифр(и только) .
тогда решение проще: пробежаться от 10^(N-1) до 10^N-1 и отобрать удовлетворяющие.
в качестве основания(10) надо рассматривать любое число, иначе при N>9 нет решения

хм, соблазн только
так если 10 элементов, то уже по два разряда для кодирования десятичным числом (2^63 есть 10^20), также соотв. двоичным и пр. основаниями - и да эдак легко пройти диапазон и отобрать подходящие, но для более 10 элементов для этого приема уже нужны спецбиблиотеки (специально оптимизированные) для работы с очень большими числами
...
Рейтинг: 0 / 0
28.02.2010, 20:04:09
| Ответить | Цитировать | Написать  
алгоритм перебора всех возможных значений
    #36493563
Фотография Пилотажный
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Пилотажный
Участник
extended - 10^4932
но медленно
...
Рейтинг: 0 / 0
28.02.2010, 20:11:55
| Ответить | Цитировать | Написать  
алгоритм перебора всех возможных значений
    #36493572
Фотография Пилотажный
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Пилотажный
Участник
Пилотажныйextended - 10^4932
но медленно
В смысле, что при преобразовании в символьный вид - в стандартных библиотеках не более 20 значимых разрядов, и нужны спецбиблиотеки, которые не быстры.
...
Рейтинг: 0 / 0
28.02.2010, 20:20:19
| Ответить | Цитировать | Написать  
25 сообщений из 27, страница 1 из 2
  1  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / алгоритм перебора всех возможных значений
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&msg=36490582&tid=1343856]:
 0ms
get settings:
 7ms
get forum list:
 20ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 476ms
get topic data:
 15ms
get forum data:
 3ms
get page messages:
 91ms
get tp. blocked users:
 2ms
others: 206ms
total:  826ms
созд. / загр.: 826ms
x
x
Закрыть


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