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

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

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


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

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

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

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

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


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

Не секрет, что при выведении на бумаге многие комбинаторные алгоритмы кажутся достаточно простыми. Например, алгоритм порождения сочетаний без повторений ( или комбинаций без повторений — различаются хотя бы одним элементом ) может быть выведен практически сходу без особенного осмысления, фактически интуитивно. Я, правда, при выписывании на листке всех сочетаний для 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. Там же есть реализации алгоритма из книги Липского.

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

                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                  Самое читаемое