Перестановка букв в слове и вывод всех возможных перестановок - C (СИ)
Формулировка задачи:
Написал программу для перестановки букв в слове и выводе всех возможных перестановок. Но при вводе слова с одинаковыми буквами он выведет одинаковые перестановки.Не подскажете как сделать так чтобы он этого не делал.
#include <stdio.h> #include <conio.h> #include <stdlib.h> #define BOOL int #define TRUE 1 #define FALSE 0 #define Len 7 int length; int* st; char* v; void Sort(char* mass, int _len) { int i,j; char tmp; for(i = 0 ; i < _len ; i++) { for(j = 0 ; j < _len - i - 1 ; j++) { if(mass[j] > mass[j+1]) { tmp = mass[j]; mass[j] = mass[j+1] ; mass[j+1] = tmp; } } } } void Initialize(char* _v,int _length) { int i; length = _length; v = (char*)malloc((length*sizeof(char))+1); st = (int*)malloc(length * sizeof(int)); for (i = 0;i<length;i++) v[i] = _v[i]; v[length] = 0; for (i = 0; i < length; i++) st[i] = 0; } void Swap(char* a, char* b) { char t = *a; *a = *b; *b = t; } void Reverse(char* v, int start) { int i; for ( i = 0; i < (length - start) / 2; i++) Swap(&(v[start + i]), &(v[length - 1 - i])); } BOOL NextPermutation() { int pos,i; if (length< 2) return FALSE; pos = length - 2; while (pos >= 0) { if (st[pos] < length- 1 - pos) { Reverse(v, pos + 1); for (i = pos + 1; i < length; ) st[i++] = 0; st[pos]++; Swap(&(v[pos]), &(v[pos + st[pos]])); return TRUE; } pos--; } return FALSE; } int main() { int k = 0,i; char mas[Len+1]; mas[Len] = 0; scanf("%s", mas); for(i = 0;mas[i]!='\0';++i) { k = i+1; } Sort(mas,k); Initialize(mas,k); do { printf("%s\n ",v); } while( NextPermutation()); getchar(); getchar(); return 0; }
при вводе caba выдает
aabc
aacb
abac
abca
acab
acba
aabc
aacb
то есть меняет местами 2 буквы а
...
а нужно
aabc
aacb
abac
abca
acab
acba
baac
baca
Уважаемые, может подскажет кто-нибудь, где ошибаюсь....?
Решение задачи: «Перестановка букв в слове и вывод всех возможных перестановок»
textual
Листинг программы
#include <stdio.h> size_t _length(char *first) { size_t len = 0; while(*first++ != '\0') ++len; return len; } void _swap(char *a, char *b) { char c = *a; *a = *b; *b = c; } void _reverse(char *first, char *last) { size_t len = _length(first); --last; for(int i = 0; i < len / 2; ++i) _swap(first++, last--); } void _sort(char *first) { size_t len = _length(first); for(int i = 0; i < len; ++i) for(int j = i; j < len; ++j) if(*(first + i) > *(first + j)) _swap(first + i, first + j); } int _next_permutation(char *first, char *last) { if (first == last) return 0; char *i = first; ++i; if (i == last) return 1; i = last; --i; for(;;) { char *ii = i; --i; if (*i < *ii) { char *j = last; while (!(*i < *--j)){} _swap(i, j); _reverse(ii, last); return 1; } if (i == first) { _reverse(first, last); return 0; } } } int main(){ char a[] = "321"; size_t len = _length(a); _sort(a); do{ for(int i = 0; i < len; ++i) printf("%c ", a[i]); printf("\n"); }while(_next_permutation(a, a + len)); return 0; }
Объяснение кода листинга программы
В данном коде реализованы функции для перестановки букв в слове и вывода всех возможных перестановок.
- Функция _length() принимает указатель на первый символ строки и возвращает количество символов в строке.
- Функция _swap() меняет местами два символа в строке.
- Функция _reverse() меняет порядок символов в строке.
- Функция _sort() сортирует символы в строке по возрастанию.
- Функция _next_permutation() генерирует следующую перестановку в строке.
- В функции main() создаётся массив символов
321
, вычисляется его длина, сортируется, генерируются и выводятся все возможные перестановки. Список функций и переменных: - _length(char *first) - функция для вычисления длины строки
- _swap(char a, char b) - функция для обмена символами в строке
- _reverse(char first, char last) - функция для перестановки порядка символов в строке
- _sort(char *first) - функция для сортировки символов в строке
- _next_permutation(char first, char last) - функция для генерации следующей перестановки в строке
- main() - основная функция программы
- a[] - массив символов для перестановки
- len - переменная для хранения длины массива a[] Вывод программы: 312 231 132 123
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д