Размышления об алгоритмах и методах. Представление полного алгоритма порождения сочетаний + размещений с повторением

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

Что я понимаю под полным описанием алгоритма и зачем это может быть нужно?


Без открытия Америки не обойтись: полный алгоритм — это та последовательность действий над объектами, которая осуществляется ручкой на бумаге. А полное описание — это каждый шаг, описанный на естественном языке, возможно, с применением дополнительных математических обозначений, но только в качестве вспомогательных. Таким образом, полное описание — это не формула и даже еще не псевдокод и, тем более, не блок-схема. Из этого очевидного тезиса следует такая же очень простая, но важная вещь — понимание реализации даже достаточно простого алгоритма может быть затруднено его сокращением или краткостью формулы. В связи с этим мне очень понравилось мнение Херба Уилфа о том, что «формула — на самом деле алгоритм», перепечатанное в данной статье Игорем Паком. Возможно, представление одних и тех же алгоритмов в виде разных формул и наблюдение за собственным восприятием этих представлений может пролить свет на то, почему одни алгоритмы мы понимаем лучше, а другие хуже.

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

Понаблюдав за собой, я обратил внимание, что бывают ситуации, когда смотришь на чужой код и вроде бы понимаешь алгоритм, знаешь язык, на котором он реализован, но не видишь всех шагов. Автор продумал для себя алгоритм, максимально сократил и таким образом фактически скрыл пошаговую реализацию для других программистов, внимание которых зачастую больше обращено на средства реализации, а все усилия направлены на поиск аналогов этих средств, необходимых для перекодирования на известный им язык.

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

Нужны ли реализации полных алгоритмов?!


Безусловно, реализации, например, полных комбинаторных алгоритмов могут работать в разы медленнее и могут быть более запутанными и некрасивыми, чем их сокращенные аналоги. На мой взгляд, подобные пошаговые реализации могут служить орудием своего рода реверс-инжиниринга, — когда нужно получить не механически переписанный с языка на язык код, а понимание всех шагов, что, кстати, в дальнейшем может послужить путём и к понимаю всех сокращений и витиеватостей в более быстрых и кратких аналогах.
Модификация представления алгоритма сочетаний без повторений

Не секрет, что при выведении на бумаге многие комбинаторные алгоритмы кажутся достаточно простыми. Например, алгоритм порождения сочетаний без повторений ( или комбинаций без повторений — различаются хотя бы одним элементом ) может быть выведен практически сходу без особенного осмысления, фактически интуитивно. Я, правда, при выписывании на листке всех сочетаний для n=5 по k=3 пару раз совершил одну и ту же ошибку, проигнорировав одно из чисел и получил неверный результат; это привело меня к мысли, что представление алгоритма на бумаге стоит осуществлять более системно, с максимальной визуализацией, с большим числом проверок при переходе от одного шага к другому, иначе то, что может быть реализовано за несколько минут, может быть растянуто на несколько часов или даже дней.

Далее мой эксперимент — представление полного алгоритма перебора сочетаний


Кратко алгоритм генерации сочетаний сформулирован так: «… в текущем сочетании найдём самый правый элемент, не достигший ещё своего наибольшего значения; тогда увеличим его на единицу, а всем последующим элементам присвоим наименьшие значения».
Источник.

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

Описание


На входе массив А=123456 (для примера), отсортированный по возрастанию; N=6 (кол-во символов в массиве); допустим, K=3,.

До входа в цикл входной массив предлагается разбить на два — B и С, В хранит значения от 1 элемента (включительно) и до K (включительно) и в C все остальное, т. е. B[123] и С[456].

1) Во внешнем цикле осуществляется перебор элемента на позиции K в В, т. е. B[K], поиск элемента большего на единицу в массиве C и обмен. Вывод на экран.

2) Далее условие — если B[K] равно N — последний элемент массива, то запускается цикл поиска элемента слева от К, для которого в массиве C есть больший на единицу. Если дошли до 0 индекса и таких элементов нет, то алгоритм завершается.

3) Если же элемент в С найден, то ищется его индекс, чтобы в дальнейшем уменьшить элемент в С на единицу, а элемент в B увеличивается на единицу. Затем массив B разбивается на два (можно без этого, см. сокр. вариант); до текущего элемента и после. Все, что после текущего элемента, переносится в массив С.
Массив B увеличивается до индекса K по возрастанию, а из массива С удаляются лишние элементы. Завершается вложенный цикл. Операции повторяются заново.


Использование этого алгоритма оказывается более затратным по времени, но хранение дополнительного массива позволяет избежать ошибок, связанных с вниманием и делает понятным более краткие реализации. В результате после разложения алгоритма на большее число шагов, у меня получилось практически сразу его закодировать.

Однако, должен предупредить, что реализация не на бумаге, а на языке, например, на PHP может показаться очень запутанной. Но, тем не менее, формально алгоритм работает правильно.

Полный нерекурсивный алгоритм порождения сочетаний (combinations) без повторений. PHP
 <?php
$a=array(1,2,3,4,5);
$k=3;
$n=5;
$c=array_splice($a, $k);
$b=array_splice($a, 0, $k);
$j=$k-1;
print_r($b);
 
        while (1) {
	   if (in_array($b[$j]+1, $c)) {
       		$m=array_search($b[$j]+1,$c);
       	     if ($m!==false) $c[$m]-=1; 
        	$b[$j]=$b[$j]+1;
               	print_r($b);
 	       
        }

       	if ($b[$k-1]==$n) {
	 $i=$k-1; 
	 while ($i >= 0) {
	 	if ($i == 0 && !in_array($b[$i]+1, $c)) {
		break 2;
		}
		if (in_array($b[$i]+1, $c)) {
       		  $m=array_search($b[$i]+1,$c);
		  if ($m!==false) $c[$m]=$c[$m]-1; 
			  $b[$i]=$b[$i]+1;
			  $f=array_splice($b, $i+1);
		          $b=array_splice($b, 0, $i+1);
			  $c=array_merge($c,$f);	
		 
			$g=$i;
		while ($g != $k-1) {
			$b[$g+1]=$b[$g]+1;
			$g++;
			}
			$c=array_diff($c,$b);
			print_r($b);
		 	     break;  
       			 }
	 	$i--;
	
		}
	
	}
	
             
}



Сокращённый вариант с комментариями

 <?php
$a=array(1,2,3,4,5);
$k=3;
$n=5;
$c=array_splice($a, $k);
$b=array_splice($a, 0, $k);
$j=$k-1;
//Вывод
	function printt($b,$k) {
	
	$z=0;
	while ($z < $k) print $b[$z++].' ';
	print "\n";
}
printt ($b,$k);
 
        while (1) {
//Увеличение на позиции K до N
       		$m=array_search($b[$j]+1,$c);
       	     if ($m!==false) {
	     	$c[$m]-=1; 
  	      	$b[$j]=$b[$j]+1;
        	       		printt ($b,$k);
       
        }
       	if ($b[$k-1]==$n) {
	 $i=$k-1; 
//Просмотр массива справа налево
	 while ($i >= 0) {
		//Условие выхода
	 	if ($i == 0 && $b[$i] == $n-$k+1) break 2;
//Поиск элемента для увеличения
       		  $m=array_search($b[$i]+1,$c);
		  if ($m!==false) { 
		  	  $c[$m]=$c[$m]-1; 
			  $b[$i]=$b[$i]+1;
		 
			$g=$i;
//Сортировка массива B по возрастанию
		while ($g != $k-1) {
			array_unshift ($c, $b[$g+1]);
			$b[$g+1]=$b[$g]+1;
			$g++;
			}
//Удаление повторяющихся значений из C
			$c=array_diff($c,$b);
				    printt ($b,$k);
		 	     break;  
       			 }
	 	$i--;
	
		}
	
	}
	
             
}

?>



Пошаговая работа кода (интервал между кадрами 20 сек.)

image

Добавление
Интересно, что данный алгоритм довольно легко модифицируется в алгоритм порождения сочетаний
с повторениями. Для этого достаточно по-другому задать массивы С и B, после удаления повторяющихся значений, на каждом проходе добавлять в С элемент под номером N. Вместо сортировки массива B по возрастанию, достаточно заполнить массив B после элемента K одним и тем же единожды увеличенным элементом.


Полный нерекурсивный алгоритм порождения сочетаний (combinations) с повторениями. PHP
Содержимое
<?php
$k=3;
$n=5;
$c=array(2,3,4,5);
$b=array(1,1,1);
$j=$k-1;
//Вывод
	function printt($b,$k) {
	
	$z=0;

	while ($z < $k) print $b[$z++].' ';
	print "\n";
}
printt ($b,$k);
 
        while (1) {
//Увеличение на позиции K до N
    
       	 if (array_search($b[$j]+1,$c)!==false ) {	     	
  	      	$b[$j]=$b[$j]+1;
        	printt ($b,$k);
       }
        
       	if ($b[$k-1]==$n) {
	 $i=$k-1; 
//Просмотр массива справа налево
	 while ($i >= 0) {
		//Условие выхода
	 	if ( $i == 0 && $b[$i] == $n) break 2;
//Поиск элемента для увеличения
       		  $m=array_search($b[$i]+1,$c);
		if ($m!==false) {
		           $c[$m]=$c[$m]-1; 
			  $b[$i]=$b[$i]+1;
		 
			$g=$i;
//Сортировка массива B 
		while ($g != $k-1) {
			array_unshift ($c, $b[$g+1]);
			$b[$g+1]=$b[$i];
			$g++;
			}
//Удаление повторяющихся значений из C
	                            $c=array_diff($c,$b);
				    printt ($b,$k);
                                    array_unshift ($c, $n);
                
		 	     break;  
       			 }
	 	$i--;
	
		}
	
	}
	
             
}

?>


Дополнение. 05.06.2017
Данный алгоритм можно использовать и для генерации размещений без повторений или с повторениями. Для генерации всех размещений с повторениями генерируем все сочетания и для каждого сочетания все перестановки. Модифицированный для этой задачи алгоритм перестановок приведен из предыдущей статьи:
Алгоритм генерации все размещений с повторениями. PHP
<?php
set_time_limit(0);
//Функция генерации всех перестановок для разбиения
function perm($b) {

$a=array_reverse($b);
       while (1) {
	   	   	print_r($a);
			print '<br/>';
		   if ($a ==$b) break;	
   $i=1;
	while($a[$i] >= $a[$i-1]) {
    $i++;
}
   $j=0;
	  while($a[$j] <= $a[$i]) {
    $j++;	
}	
	  $c=$a[$j];
	  $a[$j]=$a[$i];
	  $a[$i]=$c;
	$a=array_merge(array_reverse(array_slice($a, 0, $i)),array_slice($a, $i));	
	}
}


//Генерируем все сочетания с повторением
//установим к и n
$k=5;
$n=5;
//Установим массив
$c=array(1,2,3,4,5);
//установим массив b число единиц, в котором равно k
$b=array(1,1,1,1,1);
$j=$k-1;
//Вывод
	function printt($b,$k) {
 

	//На каждое сочетание генерируем все перестановки
perm($b);
	

}
printt ($b,$k);

 
        while (1) {
//Увеличение на позиции K до N
 
       	 if (array_search($b[$j]+1,$c)!==false ) {	     	
  	      	$b[$j]=$b[$j]+1;
        	printt ($b,$k);
       }
 
       	if ($b[$k-1]==$n) {
	 $i=$k-1; 
//Просмотр массива справа налево
	 while ($i >= 0) {
		//Условие выхода
	 	if ( $i == 0 && $b[$i] == $n) break 2;
//Поиск элемента для увеличения
       		  $m=array_search($b[$i]+1,$c);
		if ($m!==false) {
		           $c[$m]=$c[$m]-1; 
			  $b[$i]=$b[$i]+1;
 
			$g=$i;
//Сортировка массива B 
		while ($g != $k-1) {
			array_unshift ($c, $b[$g+1]);
			$b[$g+1]=$b[$i];
			$g++;
			}
//Удаление повторяющихся значений из C
	                            $c=array_diff($c,$b);
				    printt ($b,$k);
                                    array_unshift ($c, $n);
 
		 	     break;  
       			 }
	 	$i--;
 
		}
 
	}
 
 
}

?>




Лирико-практическое дополнение
Уже после написания этой статьи я оказался в библиотеке им. Ленина с томиком «Трудов по не математике» (т. I) В.А. Успенского, который в главе о Витгенштейне оставил такие строки, цитируя его самого: «Деятельность, деятельность и еще раз деятельность — вот кредо Витгенштейна. Для него процесс важнее результата. „Я открываю не результат, а тот путь, которым он достигается.“». В.А.Успенский (Витгенштейн).

Post Scriptum
Свою прошлую статью о порождении сочетаний я опубликовал преждевременно, не заметив сразу несколько ошибок, поэтому извиняюсь за свою поспешность. Реализации нерекурсивного и рекурсивного алгоритмов порождения сочетаний на разных языках были обнаружены мной на сайте rosettacode.org. Там же есть реализации алгоритма из книги Липского.
Share post
AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 21

    0
    Входной массив предлагается разбить на B[123] и С[456].

    Вы как-то всё время скачете голопом по европам, где же здесь алгоритм? Это эвристика, а не алгоритм,
    1234567 как вы на б и ц будете разбивать?
    5 пункт… э, то что вы написали… как бы помягче, для этого хватило бы и кода, мысль не понятна за руками слежу.
      0
      Да, Вы правы с 5 пунктом немного не додумал фразу. Подправил. Описание алгоритма сейчас должно почти точно отражать то, что сделано в коде.
      Вот вопросы описания и восприятия меня и волнуют, поэтому спасибо, что уделили время и прочитали.
        0
        Вы не ответили, что мы будем делать с седьмым элементом, как разбивать?
          0
          Если Вы про начальную рабивку, то
          $c=array_splice($a, $k);
          $b=array_splice($a, 0, $k);
          print_r($c);
          print_r($b);
          


          Array
          (
          [0] => 6
          [1] => 7
          )
          Array
          (
          [0] => 1
          [1] => 2
          [2] => 3
          [3] => 4
          [4] => 5

          Если про то, речь о том, что индексы считаются с 0го, то в коде определено
          j=k-1
            0
            Я вообще ничего не понял. Вы берёте от 0 до k и от k до конца?
            То есть, если k=3 n=7, то это будет b[123] c[4567], а если n =100, то b[123] c [4..100]?
              0
              Да. А как можно понять по другому то, что я написал?
                0
                Какой смысл делить массив из чёртовой тучи элементов на 3+всё остальное? На мой взгляд, с таким же успехом можно и не делить.
                  0
                  Фактически можно не делить, а только печатать до К-элемента и хранить все в одном массиве, что с одной стороны сокращает код и приближает алгоритм к каноническим реализациям, с другой стороны хотелось закодировать ровно так, как это было выведено на бумаге.
                  Для чего? Для более четкого осознания все процесса. Просто, как я уже написал, сокращённый вариант может быть не таким очевидным. Но сокращение несколько иная задач, в конце можно просто придти к такому: на Си
                  Второй вариант
              0
              Почему у вас в описании 6 бьётся на 3+3, а в коде 7 бьётся на 5+2, а не 3+4 хотя бы.
                0
                Ну это просто пример, я же тоже игрался с числами
                  0
                  По моему, он просто тролль, расходимся.
                    0
                    Я не понял, кто тролль и Вам непонятно.
                      0
                      *и что вам непонятно
            0
            Все-таки это не совсем эвристика, так как начальное и, может быть, терминальное состояние могут закономерно выбиваться из общего алгоритма, но описать ведь их надо.
            0
            Естественно разбивка зависит от K
              0
              Естественно, разбивка зависит и от N
                0
                И от К и от N вдобавок, я если меняется значения K и N, то надо не забыть поменять и массив А
              0
              В хранит значения от 0 индекса и до K включительно

              Я запутался в нумерации. Индекс отсчитывается от 0? Тогда, если К = 3, то почему в массиве В три элемента, а не четыре?
                0
                Потому что «array_splice() удаляет length элементов, расположенных на растоянии offset от начала массива ...».
                Т.е. в начале берется столько элементов, сколько указано в K
                А дальше, поскольку массив начинается с 1, а индексы считаются с 0, то
                j=k-1
                — )
                0
                В принципе можно сократить все до такого, убрав все splice внутри и убрав in_array, но очевидность относительно бумажного варианта немного теряется:
                Заголовок
                Код
                 <?php
                $a=array(1,2,3,4,5);
                $k=3;
                $n=5;
                $c=array_splice($a, $k);
                $b=array_splice($a, 0, $k);
                $j=$k-1;
                print_r($b);
                 
                        while (1) {
                	   
                       		$m=array_search($b[$j]+1,$c);
                       	     if ($m!==false) {
                	     	$c[$m]-=1; 
                        	$b[$j]=$b[$j]+1;
                               	print_r($b);	       
                        }
                
                       	if ($b[$k-1]==$n) {
                	 $i=$k-1; 
                	 while ($i >= 0) {
                
                	 	if ($i == 0 && !in_array($b[$i]+1, $c)) break 2;
                		
                       		  $m=array_search($b[$i]+1,$c);
                		  if ($m!==false) { 
                		  	  $c[$m]=$c[$m]-1; 
                			  $b[$i]=$b[$i]+1;
                			
                		 
                			$g=$i;
                		while ($g != $k-1) {
                			array_unshift ($c, $b[$g+1]);
                			$b[$g+1]=$b[$g]+1;
                			$g++;
                			}
                			$c=array_diff($c,$b);
                			print_r($b);
                		 	     break;  
                       			 }
                	 	$i--;
                	
                		}
                	
                	}
                	
                             
                }
                
                ?>
                
                

                  0
                  Согласен с основным (как я его понял) посылом статьи — для понимания работы алгоритма надо знать (прочитать, угадать) «замысел творца» — какая идея реализуется, какие инварианты соблюдаются и т.п. Так вот, все это можно описать в паре-тройке предложений в комментариях к коду — «комментируйте что а не как» (С) А саму реализацию уже надо делать краткой и оптимальной, а не рассусоливать и перегружать ненужными операциями, как в примерах статьи.

                  Only users with full accounts can post comments. Log in, please.