Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / Программирование [игнор отключен] [закрыт для гостей] / алгоритм перебора всех возможных значений / 25 сообщений из 27, страница 1 из 2
  1  все
26.02.2010, 15:40:33
    #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:49:37
    #36490445
Mozok
Mozok
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
алгоритм перебора всех возможных значений
pavlickm,

баян
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
26.02.2010, 16:26:00
    #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:32:33
    #36490541
pavlickm
pavlickm
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
алгоритм перебора всех возможных значений
Пилотажный, Mozok,
да это всё примеры на конкретных языках, мне алгоритм нужен, я ж не буду изучать хаскель что бы понять как он это делат, так же мне не очень охота лезть в исходники algorithm, что бы реализовать это у себя
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
26.02.2010, 16:49:04
    #36490582
Пилотажный
Пилотажный
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
алгоритм перебора всех возможных значений
pavlickm,
метод со вставками
с конца
1 - список пуст
2 - список 1 - вставки 21, 12
3 - два списка 21, 12 - вставки в первый 321, 231, 213, во второй 312, 132, 123
и т.д.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
26.02.2010, 22:37: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, 23:29:31
    #36491284
AIS
AIS
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
алгоритм перебора всех возможных значений
pavlickm ,
чтобы делать замечания, надо хотя бы немного почитать теорию по матиматике и программированию.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
27.02.2010, 09:29:07
    #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:36:42
    #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, 10:29:10
    #36491657
pavlickm
pavlickm
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
алгоритм перебора всех возможных значений
AIS pavlickm ,
чтобы делать замечания, надо хотя бы немного почитать теорию по матиматике и программированию.
мат е матике
что бы делать замечания на мои замечания, нужно хотя бы немного почитать теорию по орфографии русского языка. шучу =)
неохота мне читать, охота алгоритм.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
27.02.2010, 12:42:40
    #36491920
ShSerge
ShSerge
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
алгоритм перебора всех возможных значений
По сабжу: а для n=2 такие, как 11 и 22 не годятся?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
27.02.2010, 15:21:07
    #36492297
pavlickm
pavlickm
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
алгоритм перебора всех возможных значений
ShSergeПо сабжу: а для n=2 такие, как 11 и 22 не годятся?
не годятся
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
27.02.2010, 22:32:31
    #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, 23:04:56
    #36492877
ShSerge
ShSerge
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
алгоритм перебора всех возможных значений
Памас,

А чё Вы написали? Вы что, не читали, что ТС просит? Кстати, код-то ведь таки у Вас скопипащенный.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.02.2010, 00:06:26
    #36492912
Vowk
Vowk
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
алгоритм перебора всех возможных значений
Ну да, теперь по этой программе попробуй-ка словесное опесание алгоритма дать - посложнее самой программы будет в несколько раз.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.02.2010, 00:13:06
    #36492915
Vowk
Vowk
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
алгоритм перебора всех возможных значений
Что-то оно не работает. Скопировал в текстовый файл, переименовал в .html, и вот результаты (или я что-то не так делаю?)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.02.2010, 10:34:28
    #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:37:58
    #36493063
Памас
Памас
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
алгоритм перебора всех возможных значений
VowkЧто-то оно не работает. Скопировал в текстовый файл, переименовал в .html, и вот результаты (или я что-то не так делаю?)
ввод:
для N=2 12
для N=3 ABC ...
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.02.2010, 11:46:45
    #36493102
Vowk
Vowk
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
алгоритм перебора всех возможных значений
Неправильно работает программа на Javascript (обратите внимание на две последние строки)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.02.2010, 11:49:10
    #36493105
Vowk
Vowk
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
алгоритм перебора всех возможных значений
Не, таки правильно. Показалось, что одинаковые.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.02.2010, 14:59:34
    #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, 18:00:15
    #36493456
Памас
Памас
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
алгоритм перебора всех возможных значений
AISПамас... подумал что это перестановки...
А что это тогда? И ваш код, по-моему, делает упорядочные перестановки.
-- не могу сказать, что такое (НЕ)упорядочные перестановки.
-- скорость круто падает, есно, при больших N

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

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

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


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