Перестановки. Они везде. Мы постоянно что-нибудь переставляем: посуду на столе, мебель в комнате, разные аксессуары в багажнике автомобиля; нам никуда не деться от перестановок, они занимают огромную часть нашего рабочего времени:
Подозреваю, что вам уже стало скучно на вступлении, потому что оно, вероятно, напоминает текст из бюджетного документального кино рекламного характера. Я не буду утомлять вас продолжительным рассказом. Поведаю лишь краткую предысторию: я недавно просматривал различные алгоритмы на сайте rozettacode.org и в какой-то момент вышел на статью permutations, вспомнил про свой алгоритм, который я опубликовал в этой статье, и решил его доработать так, чтобы он напоминал полноценную консольную программу. Вдобавок, я внес некоторые изменения в работу самого алгоритма. Ниже будет только список доработок и сам код. Предыдущую версию алгоритма и его описание можно посмотреть по ссылке.
Кроме вышесказанного я подготовил небольшое видео (с использованием данного алгоритма) о том, как можно связывать переборные алгоритмы и алгоритмы вообще на разных языках в командной строке операционной системы Linux:
P.S. And fogive me, friends. При первой попытке код я скопировал с другого терминала, поэтому первая версия была нерабочей. Ночь, полудрема, тусклый свет… = )
Подозреваю, что вам уже стало скучно на вступлении, потому что оно, вероятно, напоминает текст из бюджетного документального кино рекламного характера. Я не буду утомлять вас продолжительным рассказом. Поведаю лишь краткую предысторию: я недавно просматривал различные алгоритмы на сайте rozettacode.org и в какой-то момент вышел на статью permutations, вспомнил про свой алгоритм, который я опубликовал в этой статье, и решил его доработать так, чтобы он напоминал полноценную консольную программу. Вдобавок, я внес некоторые изменения в работу самого алгоритма. Ниже будет только список доработок и сам код. Предыдущую версию алгоритма и его описание можно посмотреть по ссылке.
- Алгоритм теперь полноценно выводит объекты слева направо в лексикографическом порядке
(признаюсь, у меня не сразу получилось «развернуть» алгоритм). - Программа теперь обязательно требует ввода аргумента, аргументом могут быть цифры, английский алфавит (в верхнем и нижнем регистре) и другие символы юникода.
- В связи с пунктом №2 в код добавлен алгоритм сортировки пузырьком, поэтому больше можно не заботиться о порядке ввода, главное, уникальность символов.
- Теперь есть возможно порождать и перестановки с повторением, добавив всего два символа "=" в код (условие двух первых циклов основного алгоритма). Т.е. алгоритм может работать с двумя типами объектов. Единственное: при порождении перестановок с повторениями после вывода последнего объекта алгоритм еще пытается работать и печатает лишний вывод.
- Остановка работы осуществляется по номеру перестановки, вычисляется через факториал.
Кроме вышесказанного я подготовил небольшое видео (с использованием данного алгоритма) о том, как можно связывать переборные алгоритмы и алгоритмы вообще на разных языках в командной строке операционной системы Linux:
Код С
#include <stdio.h>
int main (int argc, char *argv[]) {
//here we check arguments
if (argc < 2) {
printf("Enter an argument. Example 1234 or dcba:\n");
return 0;
}
//it calculates an array's length
int x;
for (x = 0; argv[1][x] != '\0'; x++);
//buble sort the array
int f, v, m;
for(f=0; f < x; f++) {
for(v = x-1; v > f; v-- ) {
if (argv[1][v-1] > argv[1][v]) {
m=argv[1][v-1];
argv[1][v-1]=argv[1][v];
argv[1][v]=m;
}
}
}
//it calculates a factorial to stop the algorithm
char a[x];
int k=0;
int fact=k+1;
while (k!=x) {
a[k]=argv[1][k];
k++;
fact = k*fact;
}
a[k]='\0';
//Main part: here we permutate
int i, j;
int y=0;
char c;
while (y != fact) {
printf("%s\n", a);
i=x-2;
while(a[i] > a[i+1] ) i--;
j=x-1;
while(a[j] < a[i] ) j--;
c=a[j];
a[j]=a[i];
a[i]=c;
i++;
for (j = x-1; j > i; i++, j--) {
c = a[i];
a[i] = a[j];
a[j] = c;
}
y++;
}
}
P.S. And fogive me, friends. При первой попытке код я скопировал с другого терминала, поэтому первая версия была нерабочей. Ночь, полудрема, тусклый свет… = )
Комментарии (8)
dcc0 Автор
03.05.2018 08:43-1Код перепостил, бьютифаер как-то странно форматнул его. И я в ночи не заметил что еще и что-то лишнее при копипасте зацепил.: ) Сорри если вы тестировали и он не запустился =)
kez
03.05.2018 14:25+1Для (визуальных) эстетов
Правильный бьютифаер (с пробелами, с табами не пускает хабр)#include <stdio.h> int main (int argc, char *argv[]) { //here we check arguments if (argc < 2) { printf("Enter an argument. Example 1234 or dcba:\n"); return 0; } //it calculates an array's length int x; for (x = 0; argv[1][x] != '\0'; x++); //buble sort the array int f, v, m; for(f=0; f < x; f++) { for(v = x-1; v > f; v-- ) { if (argv[1][v-1] > argv[1][v]) { m=argv[1][v-1]; argv[1][v-1]=argv[1][v]; argv[1][v]=m; } } } //it calculates a factorial to stop the algorithm char a[x]; int k=0; int fact=k+1; while (k!=x) { a[k]=argv[1][k]; k++; fact = k*fact; } a[k]='\0'; //Main part: here we permutate int i, j; int y=0; char c; while (y != fact) { printf("%s\n", a); i=x-2; while(a[i] > a[i+1] ) i--; j=x-1; while(a[j] < a[i] ) j--; c=a[j]; a[j]=a[i]; a[i]=c; i++; for (j = x-1; j > i; i++, j--) { c = a[i]; a[i] = a[j]; a[j] = c; } y++; } }
mersinvald
И зачем это на хабре?
P.S код — полный швах
dcc0 Автор
Есть люди, которым эта тематика интересна.
Не принуждаю вас к чтению.
По поводу кода, что именно швах?
Что там в stdio может быть такого, что вызывает столько эмоций?
Или не нравится само оформление, имена переменных и т.д.?
А то как из кинотеатра вышли со словами «фильм фигня» = )
mersinvald
Ну вот, видишь, ты и сам понимаешь в чем проблема: в оформлении и именах переменных. И в абсолютнои остутствии разбиения на логические части, портянка как она есть.
Еще меня терзают сомнения насчет необходимости количества проходов по массиву, которые ты делаешь.
dcc0 Автор
Вот! Это конструктивно. Спасибо за ответ. Имена переменных выбраны специально максимально короткие (Мне нравится так писать). Соглашусь, наверное, что надо бы разделить код на части более наглядно, но я обозначаю комментарием это деление. Спорно, но можно согласиться. Конечно бы, сейчас думаю поменять немножко стиль, раз столько критики, по крайней мере, наверно, стоит выносить все переменные в какой-то один блок. Спасибо, что ответили = )