C++ Recursion: Dinner party seating arrangement

Question

The dinner_shuffles method should return all possible arrangements of n dinner guests as a vector of strings. The names used should be the first n names as designated in the constructor.

The ends of the string represent the adjacent end chairs of the circular table.

The order of the dinner guest arrangements is not specified.

Here is a simple example. If the dinner guests are abcde, then the result of dinner_shuffles(3) will be:

abc

acb

bac

bca

cab

cba

dinner guest names are fed is as a string
Even knowing the equation that defines this recursive relationship would be VERY helpful thanks

** UPDATE: I have figured out that the Fibonacci sequence is as follows for the number of combinations: F(n) = F(n-1) + F(n-2) - 2. I'm new to c++ and am unsure as to how I can visualize this using letter representation.

You could try http://en.cppreference.com/w/cpp/algorithm/next_permutation — Ben Cottrell, Apr 01 '18 at 21:06
Looks like homework, have tried anything? If yes show us some code. — TioneB, Apr 01 '18 at 21:25
Imagine you have a list of four dinner guests `{a, b, c, d}`, and your assistant can draw up a list of all arrangements of any three guests you specify. How would you construct the list of all arrangements of four? — Beta, Apr 01 '18 at 21:33
Hi all, so I was able to figure out the Fibonacci sequence and it is as follows: F(n) = F(n-1) + F(n-2) -2. I used a recursive formula to come up with the number of combinations but now I just need some help figuring out how to visualize those using strings. I'll update the main post with this information as well. — Megan Heydari, Apr 01 '18 at 22:56
can you write a recursive function that returns the factorial of an int argument? — jackw11111, Apr 01 '18 at 23:35
What does the Fibonacci sequence have to do with this problem? — meowgoesthedog, Apr 01 '18 at 23:55
The Fibonacci sequence allows you to determine the number of combinations (i.e. seating arrangements) for each value of n. — Megan Heydari, Apr 02 '18 at 00:35

score 0 · Answer 1 · answered Apr 02 '18 at 07:25

Even knowing the equation that defines this recursive relationship would be VERY helpful thanks

The equation goes something like this:

If the length of the string is 1, return the arrangement (base case).
Otherwise, give each character a turn at being in the first position and recursively call the rest of the string with that character removed.

This question is the same thing, by checking if there is 1 person standing, there is only one choice left, otherwise produce all the arrangements that the next seat can be sat on by.

Try stepping through this simplified code here if it still doesn't make sense.

Otherwise, have a look at this solution:

#include <iostream>
#include <vector>
using namespace std;

vector<string> arrangements;

class Table
{
public:
    string seated = "";
    string notSeated = "";

    Table(string n);
    vector<string> dinner_shuffles(int n);
};

Table::Table(string n)
{
  seated = "";
  notSeated = n;
}

vector<string> Table::dinner_shuffles(int n)
{
    //The names used should be the first n names as designated in the constructor.
    notSeated = notSeated.substr(0, n);

  if (notSeated.length() == 1)
  {
    arrangements.push_back(seated+notSeated);
  }
  for (int i = 0; i < notSeated.length(); i++)
  {
    Table newArrangement(notSeated.substr(0,i) + notSeated.substr(i+1, notSeated.length()));
    newArrangement.seated = seated + notSeated[i];
    newArrangement.dinner_shuffles(n);
  }
   //return all possible arrangements of n dinner guests as a vector of strings.
  return arrangements;
}

int main()
{
    //dinner guest names are fed in as a string
    string notSeated = "abcde";
    Table table(notSeated);

    vector<string> vals = table.dinner_shuffles(3);

    //abc, acb, bac, bca, cab, cba
    for (int i = 0; i < vals.size(); i++){
        cout << vals[i] << endl;
    }
    return 1;
}

C++ Recursion: Dinner party seating arrangement

1 Answers1