перестановки строки в порядке возрастания

Question

Написать программу для формирования перестановок строк, взяв следующим образом: ввода: ABCD
Выход:

A 
AB 
AC 
AD 
ABC 
ACD 
ABCD 
B 
BC 
BD 
BCD 
C 
CD 
D 

Но я попытался с помощью назад отслеживания алгоритма в языке Си:

#include <stdio.h> 

/* Function to swap values at two pointers */ 
void swap(char *x, char *y) 
{ 
    char temp; 
    temp = *x; 
    *x = *y; 
    *y = temp; 
} 

void permute(char *a, int i, int n) 
{ 
    int j; 
    if(i == n) 
     printf("%s\n", a); 
    else 
    { 
     for(j = i; j <= n; j++) 
     { 
      swap((a + i), (a + j)); 
      permute(a, i + 1, n); 
      swap((a + i), (a + j)); //backtrack 
     } 
    } 
} 

int main() 
{ 
    char a[] = "ABC"; 
    permute(a, 0, 2); 
    getchar(); 
    return 0; 
} 

Вход: ABC

Выход:

ABC 
ACB 
BAC 
BCA 
CBA 
CAB 

Но мне нужна программа для только указанного порядка, как

A 
AB 
AC 
ABC 
B 
BC 
C 

Answer 1

В вашем примере строки не в порядке возрастания: у вас есть AB, AC, AD, ABC, ..., но то у вас есть B, BC до C и D. Если вы хотите, чтобы он в алфавитном порядке был A, AB, ABC, ABCD, AC, ...

Когда вы пишете так, вы видите рекурсивную структуру ... просто возьмите A в первой половине списка, и вы должны получить вторую. Таким образом, вы можете легко написать рекурсивную программу, которая делает что-то вроде

permute("ABCD"): 
    print ("A" + everything in permute("BCD")) 
    print (everything in permute("BCD"))