0

I found several examples of what I was looking to do, but none worked quite exactly how I wanted, of course.

I'm trying to modify the following program to display all possible combinations of a string of words. So, for example:

*str = "one two"; // would be:
one two
two one

*str = "one two three"; // would be:
one two three
one three two

two one three
two three one

three one two
three two one

etc..

Here is what I am working with, which produces duplicates as well, which I do not want.

#include <stdio.h>
#include <string.h>

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

/* Function to print permutations of string
   This function takes three parameters:
   1. String
   2. Starting index of the string
   3. Ending index of the string. */
void permute(char *a, int l, int r)
{
   int i;
   if (l == r)
     printf("%s\n", a);
   else
   {
       for (i = l; i <= r; i++)
       {
          swap((a+l), (a+i));
          permute(a, l+1, r);
          swap((a+l), (a+i)); //backtrack
       }
   }
}

/* Driver program to test above functions */    
int main()
{
    char str[] = "one two three";
    int n = strlen(str);
    permute(str, 0, n-1);
    return 0;
}
Phyllis Dillion
  • 9
  • 1
  • 2
    Have a read of `std::next_permutation` http://en.cppreference.com/w/cpp/algorithm/next_permutation – Richard Critten Feb 13 '18 at 21:58
  • 2
    The [tag:c++] tag appears to have no place in this question. – Fred Larson Feb 13 '18 at 21:58
  • 3
    Are you asking for a c or a c++ solution? They will likely be very different. – François Andrieux Feb 13 '18 at 21:59
  • Do you want to permute words or characters? Right now you are not considering the words. – Pablo Feb 13 '18 at 22:08
  • This program seems correct, but it makes permutation of the characters. If you want to make permutations of words, you just have to modify it to work on an array of words. – giusti Feb 13 '18 at 22:08
  • 1
    Seems like the example has some typos, e.g. `two three two` doesn't seem right. – user3386109 Feb 13 '18 at 22:20
  • Corrected. Yes, I was hoping for a C solution, not C++. It works with letters, but I do not know how to make it work words only. – Phyllis Dillion Feb 13 '18 at 22:23
  • Since the string has three words, I would create a string with three letters, e.g. `"abc"`. Then permute the letters. When it comes time to print, substitute the words for the letters. For example, print "one" instead of "a", etc. – user3386109 Feb 13 '18 at 22:29
  • @user3386109 : you have made a simple problem over-complicated. Split the string at the space-delimiters (using strtok() for example) and simply generate permutations of the _pointers_ to each word. – Clifford Feb 13 '18 at 23:19
  • _Yes, I was hoping for a C solution_: hmm, so why did you use the C++ tag in first place? – Jabberwocky Feb 13 '18 at 23:23
  • @Clifford Your solution runs into problems when starting with a string that contains duplicates, like `"one two one three"`. – user3386109 Feb 13 '18 at 23:28
  • @user3386109 : They are distinct strings - the OP is not clear about what is required. If that is the requirement then he first has to generate the _set of unique words_. I am not sure how your suggestion solves the problem of duplication either - the association of letter to locations in the string is hard to implement or strings of an arbitrary number of words. – Clifford Feb 13 '18 at 23:35
  • Dumping [somone else's code](https://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/) verbatim and without attribution then asking how to adapt it to solve a different (and ambiguously defined) problem does not make for a good question. – Clifford Feb 13 '18 at 23:38

1 Answers1

1

Instead of

char str[] = "one two three";

try starting with

char *strs[3];
strs[0] = "one";
strs[1] = "two";
strs[2] = "three";

And then modify your existing algorithm to work with that.

Stephen Docy
  • 4,738
  • 7
  • 18
  • 31