2n ambassadors are invited to a meeting. Every ambassador has at most n-1 enemies. Devise an algorithm to prove that the ambassadors can be seated around a table, so that nobody sits next to an enemy.note: the table is round

Printable View

- 08-06-2010marcuspaxi need help with this question:
2n ambassadors are invited to a meeting. Every ambassador has at most n-1 enemies. Devise an algorithm to prove that the ambassadors can be seated around a table, so that nobody sits next to an enemy.note: the table is round

- 08-06-2010laserlight
What have you tried?

- 08-06-2010marcuspax
am a beginner with c programming,i haven`t tried anything,but i`ll look up the links,thanx

- 08-06-2010whiteflags
Isn't this a sorting problem? All you have to do is make sure person A doesn't hate B and sort on that criteria.

- 08-06-2010quzah
Can A1 be A2's enemy without A2 being A1's enemy?

Quzah. - 08-06-2010Elysia
The first step is to formulate an algorithm for the task. That has nothing to do with C.

- 08-11-2010new_ink2001
Marcus,

I apologize that it's taken me so long to reply. The question's solution pertains to a topic in mathematics, namely matching. The general summary is to match the ambassador's to seats which meet the "nobody sits next to an enemy" requirement/constraint. Something that programmers do deal with or if not then the engineer stays late leaving detailed instructions.... The proof that it can be accomplished is given by the chromatic number of the graph, that is the number of colors required so that no two neighbors have the same color. If every ambassador had n-1 enemies, it would leave n+1 potential neighbors...etc.

I've been tinkering with some solutions for a seating chart in C code, and I'll have something posted to look at soon. The text books I am using are: Dossey, et. al.__Discrete Mathematics__3rd Ed. and Cormen, et. al.__Introduction to Alogrithms__2nd Ed. Frankly, I am rather flattered that you would expect a programmer to deal with these problems, and it's part of why I got into mathematics.

By the way Quzah, the ambassadors are not assassins so the edges are bi-directional. Where did you find the question Marcus? To address Elysia's point, it may have been more appropriately placed in the networking board or non-programming board...I'm not sure either.

Best Regards,

New Ink -- Henry - 08-13-2010new_ink2001
Marcus,

Again I apologize about taking so long to close this thread. I've only been able to spend a couple hours a day on it, and I didn't find the thread until the 10th (Tues.). So I read through the text books, and found that the matching problems are the right sort. Although the problem lends itself to a little bit of guessing, and I think maybe I should have checked in with an Operations Research text...

So rather than attempting to populate the seats directly while reading the enemy list, I chose to approach the seating with an ideal arrangement (which happened to be a maximal matching) and apply the enemy constraints via a series of row swaps. I don't get to do these a lot lately, so suggestions are welcome, and I look forward to reading any replies.

I tested it with some small inputs, and it produced a completely accurate seating chart every time. The input files I wrote, produced bugs because the text encoding in my editor and the command line are different...I'd like any suggestions about that one.

Here is the algorithm:

Read the enemy matrix.

Assume a seating chart (a maximal matching between ambassadors and seats).

For every contradictory seating arrangement, swap seats until there is no contradiction.

The code that implements this:

Code:`#include <stdio.h>`

#include <stdlib.h>

#define MAX_LINE 256

#define TRUE 1==1

#define FALSE 1==0

int **createMatrix(int rows, int columns);

int **createIdentity( int rows );

void releaseMatrix( int **mat, int rows, int columns );

int **readAdjacency( FILE *fp, int *rows, int *columns );

int getNeighbors( int **mat, int rows, int columns, int ambassador /* zero index */, int *neighbors );

int getRowWithOne( int **mat, int rows, int column );

int getColWithOne( int **mat, int columns, int row );

void rowSwap( int **mat, int columns, int swap1 /* zero index */, int swap2 );

void printSeating( int **mat, int rows, int columns );

int main()

{

int **enemies;

int **seats;

int neighbors[2];

int current_seat;

int rows;

int hostile;

int j;

int k;

enemies = readAdjacency( stdin, &rows, &rows ); // enemy list

seats = createIdentity( rows ); // ideal seating

// adjust from the ideal seating to a conflict free arrangement

for( j = 0; j < rows; j++ )

{

current_seat = getNeighbors( seats, rows, rows, j, neighbors );

// always != -1 since started with ideal

if( TRUE == enemies[j][ neighbors[0] ] || TRUE == enemies[j][ neighbors[1] ] )

{

// currently seated with an enemy

hostile = TRUE;

}

while( hostile )

{

// swap until seated with an acceptable partners

for( k = 0; k < rows && hostile; k++ )

{

rowSwap( seats, rows, current_seat, k );

current_seat = getNeighbors( seats, rows, rows, j, neighbors );

if( FALSE == enemies[j][ neighbors[0] ] && FALSE == enemies[j][ neighbors[1] ] )

{

hostile = FALSE;

}

}

}

}

printSeating( seats, rows, rows );

releaseMatrix( enemies, rows, rows );

releaseMatrix( seats, rows, rows );

return 0;

}

// read from fp. formatted:

// 2n\n

// Ai Ak Aj ... An-1\n

// ...

// EOF (ctrl+d)

// Where 2n, A are integer's

int **readAdjacency( FILE *fp, int *rows, int *columns )

{

int **mat;

int reading;

int selected;

int j;

int k;

int rd;

int water;

char buffer[MAX_LINE];

fscanf( fp, "%d\n", &k );

*rows = k;

*columns = k;

mat = createMatrix( k, k );

selected = FALSE;

water = 0;

reading = TRUE;

while( ! feof( fp ) && reading )

{

rd = fgetc( fp );

switch( rd )

{

case EOF: // end of input

reading = FALSE;

case '\n': // next ambassador

if( FALSE == selected ) // if we weren't reading one...finished

{

reading = FALSE;

}

else // update

{

buffer[water] = '\0';

k = atoi( buffer ) - 1;

water = 0;

mat[j][k] = mat[k][j] = TRUE; // not a friendly ambassador

selected = FALSE;

}

break;

case '\t': // next number

if( FALSE == selected )

{

selected = TRUE;

buffer[water] = '\0';

j = atoi( buffer ) - 1;

water = 0;

}

else

{

buffer[water] = '\0';

k = atoi( buffer ) - 1;

water = 0;

mat[j][k] = mat[k][j] = TRUE; // not a friendly ambassador

}

break;

default: // current number

buffer[water++] = rd;

}

}

return mat;

}

int **createMatrix(int rows, int columns)

{

int **mat;

int j;

int k;

mat = (int**) malloc( rows * sizeof(int*) );

if( NULL == mat )

{

fprintf( stderr, "Problem allocating memory in createMatrix...exiting." );

exit( 1 );

}

for( j = 0; j < rows; j++ )

{

mat[j] = (int*) malloc( columns * sizeof(int) );

if( NULL == mat[j] )

{

fprintf( stderr, "Problem allocating memory in createMatrix...exiting." );

for( k = j-1; k >= 0; k-- )

{

free(mat[k]);

}

free(mat);

exit( 1 );

}

for( k = 0; k < columns; k++ )

{

mat[j][k] = FALSE; // populate with zeros

}

}

return mat;

}

int **createIdentity( int rows )

{

int **identity = createMatrix( rows, rows );

while(rows > 0)

{

identity[rows - 1][rows - 1] = TRUE;

rows--;

}

return identity;

}

void releaseMatrix( int **mat, int rows, int columns )

{

int j;

if( NULL == mat )

{

return;

}

for( j = 0; j < rows; j++ )

{

free( mat[j] );

}

free( mat );

return;

}

void rowSwap( int **mat, int columns, int row1 /* zero index */, int row2 )

{

int temp;

while( 0 < columns )

{

temp = mat[row1][columns - 1];

mat[row1][columns - 1] = mat[row2][columns - 1];

mat[row2][columns - 1] = temp;

columns--;

}

return;

}

int getNeighbors( // -1 if there is not any seat assigned

int **mat, // seating chart

int rows, // size information

int columns,

int ambassador /* zero index */, // ambassador of interest

int *neighbors ) // current pair of ambassador's adjacent

{

int seat;

seat = getRowWithOne( mat, rows, ambassador );

if( -1 != seat )

{

if( 0 == seat )

{

neighbors[0] = getColWithOne( mat, columns, rows -1 );

}

else

{

neighbors[0] = getColWithOne( mat, columns, seat-1 );

}

neighbors[1] = getColWithOne( mat, columns, (seat + 1) % rows );

}

return seat;

}

int getRowWithOne( int **mat, int rows, int column )

{

int result = -1;

int j;

for( j = 0; j < rows; j++ )

{

if( 1 == mat[j][column] )

{

result = j;

return result;

}

}

return result;

}

int getColWithOne( int **mat, int columns, int row )

{

int result = -1;

int j;

for( j = 0; j < columns; j++ )

{

if( 1 == mat[row][j] )

{

result = j;

return result;

}

}

return result;

}

void printSeating( int **mat, int rows, int columns )

{

int j, k;

fprintf( stdout, " " );

for( j = 0; j < columns; j++ )

{

fprintf( stdout, "A%d ", j+1 );

}

fprintf( stdout, "\n" );

for( j = 0; j < rows; j++ )

{

fprintf( stdout, "S%d ", j+1 );

for( k = 0; k < columns; k++ )

{

fprintf( stdout, " %d ", mat[j][k] );

}

fprintf( stdout, "\n" );

}

return;

}

Code:`Script started on Fri Aug 13 18:54:46 2010`

]0;~

[32mHenry@local-a3120676b [33m~[0m

$ gcc -g ambassadors2.c

]0;~

[32mHenry@local-a3120676b [33m~[0m

$ ./a.exe

4

1 2

3 4

A1 A2 A3 A4

S1 0 1 0 0

S2 0 0 1 0

S3 1 0 0 0

S4 0 0 0 1

]0;~

[32mHenry@local-a3120676b [33m~[0m

$ exit

exit

Script done on Fri Aug 13 18:55:23 2010

Best Regards,

New Ink -- Henry - 08-14-2010Salem
No worries.

The OP hasn't been back since it became obvious to all that they weren't going to get their homework done for them in time. - 08-14-2010new_ink2001
Salem,

No kidding. I thought this was a rather elegant solution, but I wonder what the OP came up with.... It was a little early to optimize when I got it running, but I think that one could replace the enemy list with an adjacency list to save some space. Of course, then the measuring the constraints portion of the algorithm would look different. And I left a #define from an earlier revision about a maximum line that is superfluous....

Best Regards,

New Ink -- Henry - 08-14-2010new_ink2001
Whiteflags,

Yes it is a sorting problem in that sorting is a matching problem. Rather than using the ordering principle on real numbers, the ordering requirement is derived from the enemy list.

Best Regards,

New Ink -- Henry - 08-14-2010Salem
The elegance (or otherwise) is immaterial.

The fact is, it's a TOTAL answer that some lazy sod is just going to hand in without so much as a bean of effort on their part. But hey, it's your free time, you can do what you want.

Perhaps you would be interested in nurse-maiding them when they get a job, based on the worthless qualification obtained by getting others to do their homework.

I've had to suffer from clueless dolts who couldn't find their ass in the dark, and I've no interest in pushing more clueless people into the workplace.

There is a very simple rule on this forum (and most others as well). Our effort matches their effort.

If someone shows up with a copy/paste question, then all they'll get is a copy/paste answer.

> but I wonder what the OP came up with

ROFLMAO - you're kidding right? - 08-14-2010AdakQuote:

I've had to suffer from clueless dolts who couldn't find their ass in the dark, and I've no interest in pushing more clueless people into the workplace.

< just kidding, of course! >

The problem reminds me a lot of a Sudoku puzzle. Very constrained guest/number placement. - 08-15-2010new_ink2001What I want...
Salem,

I agree that my time may be better spent, but I haven't landed a contract since I signed up on the contracting boards (e.g. ELance, vWorker, Freelancer, ...etc.) a few years ago. I can't even get HR to call me back most of the time. I'm mostly interested in building a little bit of background, and actually getting something done rather than getting shot down in the proposal stage.

It does a little, in that it is a measure of my sophistication, and desire to learn. At least, I think. If nothing else, it saves a lot of time during the maintenance phase of the life-cycle.

Absolutely not, no sir. And to quote myself from other boards: If this does happen to relate to graded work, if any, I never got into plagiarism because it is a question of honour. If that isn't enough to complete the premise, I must also point out that one can not take us to the test...or any other controlled environment like a safe room. It's nice to see an answer though...I can appreciate that myself. From what I read that's what these boards are for.... I verified that with the guidelines and faq.

Then you've accomplished more success than I. I didn't put up with them, and I didn't push either. I haven't been gainfully employed in this field for about five years now, because it would seem that what those "...clueless dolts..." lack in ability, they make up for with slander and poor management decisions. Perhaps, I could get one of those persuasive references that they issue with cold blooded precision?

If I find the question on the board, I assume it is fair game. I will check out the references you are suggesting, but occasionally it edifies my need to be able to brag to recruiters when I can refer to a venue such as this. Especially when I come across like a dinosaur to some of the hack and slashers that treat elegance as vanity -- rather than realize that the maintenance phase of the software life cycle is supposed to go for a while.

Now, before this starts sounding like a support group, I was thinking about the constraints on the problem. If there were an odd number of ambassadors, I don't think it is deterministically possible (in the worst case). Would anyone care to debate that point? I'm rather confident that one could use the chromatic number of the graph to complete the proof, but I've got a lot on my plate at the moment...trying to blend in.

Best Regards,

New Ink -- Henry - 08-15-2010new_ink2001
By the way, thank you for the guidance. I really appreciate it.

Best Regards.