Issues with understanding Dining table optimal seating algorithm












6















I was reading through a problem and was trying to solve this problem.




You've invited N people over for dinner. Let's say 4.



You have a circular dinner table and you wish to seat everyone around
it. Unfortunately, not all of your friends are friends with each
other, but you'd like to seat everyone optimally so that as many
people as possible are seated next to people they consider friends and
not enemies.



You've charted everyone's friendships and hatreds in a matrix of size
NxN and represented friendships with the integer 1, hatreds with -1,
and sheer indifference with 0.




[[ 0, 1, 1, 1, 1],    ← yes you like all your friends
[-1, 0, 1,-1, 0],
[-1, 1, 0, 1, 0],
[ 1, 1, 1, 0,-1],
[ 1, 0, 0,-1, 0]]


Question:




-> Write a Javascript method that computes an optimal seating arrangement as an Array, e.g. [0,4,2,1,3], for a given input matrix. (assuming indexes 0
and N-1 are seated adjacently). What is the time complexity for the
solution? Add thoughts on possible optimizations.




I've tried solving this manually however, I didn't understand the question's example [0,4,2,1,3] for the given input matrix.



Can someone Enlighten me?



How did he/she come up with [0,4,2,1,3]?



Thanks and very much appreciate your time.










share|improve this question









New contributor




SFer is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
















  • 1





    You are row and column 0, you like all your friends, but only your friends 2 and 3 like you, "friends" 1 and 2 dislike you (-1 in column 0 - that's your own popularity). The expample means the sitting order: You, next to you friend 4, then 2, 1, 3 which is on the other side next to you.

    – Quasimodo's clone
    3 hours ago








  • 2





    The problem statement seems too vague; if the goal is that "as many people as possible are seated next to people they consider friends and not enemies", how do we quantify that? For example: suppose that one arrangement has each guest adjacent to one person they like and one person they hate, and a different arrangement has each guest adjacent to two people they're neutral about. Which of these is considered better?

    – ruakh
    3 hours ago






  • 2





    i dont think [0,4,2,1,3] is the answer, its the desired output structure, maybe, that s/he is looking for? 🤔

    – Emma
    3 hours ago








  • 2





    @ruakh sure. I'm guessing its an open ended question. Can you make an assumption and come up with a possible outcome?

    – SFer
    2 hours ago






  • 2





    I'm not sure if I want to have dinner with these folks, not if my first two "friends" don't like me back!

    – Scott Sauyet
    2 hours ago


















6















I was reading through a problem and was trying to solve this problem.




You've invited N people over for dinner. Let's say 4.



You have a circular dinner table and you wish to seat everyone around
it. Unfortunately, not all of your friends are friends with each
other, but you'd like to seat everyone optimally so that as many
people as possible are seated next to people they consider friends and
not enemies.



You've charted everyone's friendships and hatreds in a matrix of size
NxN and represented friendships with the integer 1, hatreds with -1,
and sheer indifference with 0.




[[ 0, 1, 1, 1, 1],    ← yes you like all your friends
[-1, 0, 1,-1, 0],
[-1, 1, 0, 1, 0],
[ 1, 1, 1, 0,-1],
[ 1, 0, 0,-1, 0]]


Question:




-> Write a Javascript method that computes an optimal seating arrangement as an Array, e.g. [0,4,2,1,3], for a given input matrix. (assuming indexes 0
and N-1 are seated adjacently). What is the time complexity for the
solution? Add thoughts on possible optimizations.




I've tried solving this manually however, I didn't understand the question's example [0,4,2,1,3] for the given input matrix.



Can someone Enlighten me?



How did he/she come up with [0,4,2,1,3]?



Thanks and very much appreciate your time.










share|improve this question









New contributor




SFer is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
















  • 1





    You are row and column 0, you like all your friends, but only your friends 2 and 3 like you, "friends" 1 and 2 dislike you (-1 in column 0 - that's your own popularity). The expample means the sitting order: You, next to you friend 4, then 2, 1, 3 which is on the other side next to you.

    – Quasimodo's clone
    3 hours ago








  • 2





    The problem statement seems too vague; if the goal is that "as many people as possible are seated next to people they consider friends and not enemies", how do we quantify that? For example: suppose that one arrangement has each guest adjacent to one person they like and one person they hate, and a different arrangement has each guest adjacent to two people they're neutral about. Which of these is considered better?

    – ruakh
    3 hours ago






  • 2





    i dont think [0,4,2,1,3] is the answer, its the desired output structure, maybe, that s/he is looking for? 🤔

    – Emma
    3 hours ago








  • 2





    @ruakh sure. I'm guessing its an open ended question. Can you make an assumption and come up with a possible outcome?

    – SFer
    2 hours ago






  • 2





    I'm not sure if I want to have dinner with these folks, not if my first two "friends" don't like me back!

    – Scott Sauyet
    2 hours ago
















6












6








6


1






I was reading through a problem and was trying to solve this problem.




You've invited N people over for dinner. Let's say 4.



You have a circular dinner table and you wish to seat everyone around
it. Unfortunately, not all of your friends are friends with each
other, but you'd like to seat everyone optimally so that as many
people as possible are seated next to people they consider friends and
not enemies.



You've charted everyone's friendships and hatreds in a matrix of size
NxN and represented friendships with the integer 1, hatreds with -1,
and sheer indifference with 0.




[[ 0, 1, 1, 1, 1],    ← yes you like all your friends
[-1, 0, 1,-1, 0],
[-1, 1, 0, 1, 0],
[ 1, 1, 1, 0,-1],
[ 1, 0, 0,-1, 0]]


Question:




-> Write a Javascript method that computes an optimal seating arrangement as an Array, e.g. [0,4,2,1,3], for a given input matrix. (assuming indexes 0
and N-1 are seated adjacently). What is the time complexity for the
solution? Add thoughts on possible optimizations.




I've tried solving this manually however, I didn't understand the question's example [0,4,2,1,3] for the given input matrix.



Can someone Enlighten me?



How did he/she come up with [0,4,2,1,3]?



Thanks and very much appreciate your time.










share|improve this question









New contributor




SFer is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.












I was reading through a problem and was trying to solve this problem.




You've invited N people over for dinner. Let's say 4.



You have a circular dinner table and you wish to seat everyone around
it. Unfortunately, not all of your friends are friends with each
other, but you'd like to seat everyone optimally so that as many
people as possible are seated next to people they consider friends and
not enemies.



You've charted everyone's friendships and hatreds in a matrix of size
NxN and represented friendships with the integer 1, hatreds with -1,
and sheer indifference with 0.




[[ 0, 1, 1, 1, 1],    ← yes you like all your friends
[-1, 0, 1,-1, 0],
[-1, 1, 0, 1, 0],
[ 1, 1, 1, 0,-1],
[ 1, 0, 0,-1, 0]]


Question:




-> Write a Javascript method that computes an optimal seating arrangement as an Array, e.g. [0,4,2,1,3], for a given input matrix. (assuming indexes 0
and N-1 are seated adjacently). What is the time complexity for the
solution? Add thoughts on possible optimizations.




I've tried solving this manually however, I didn't understand the question's example [0,4,2,1,3] for the given input matrix.



Can someone Enlighten me?



How did he/she come up with [0,4,2,1,3]?



Thanks and very much appreciate your time.







javascript algorithm data-structures






share|improve this question









New contributor




SFer is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.











share|improve this question









New contributor




SFer is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.









share|improve this question




share|improve this question








edited 3 hours ago







SFer













New contributor




SFer is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.









asked 3 hours ago









SFerSFer

312




312




New contributor




SFer is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.





New contributor





SFer is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.






SFer is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.








  • 1





    You are row and column 0, you like all your friends, but only your friends 2 and 3 like you, "friends" 1 and 2 dislike you (-1 in column 0 - that's your own popularity). The expample means the sitting order: You, next to you friend 4, then 2, 1, 3 which is on the other side next to you.

    – Quasimodo's clone
    3 hours ago








  • 2





    The problem statement seems too vague; if the goal is that "as many people as possible are seated next to people they consider friends and not enemies", how do we quantify that? For example: suppose that one arrangement has each guest adjacent to one person they like and one person they hate, and a different arrangement has each guest adjacent to two people they're neutral about. Which of these is considered better?

    – ruakh
    3 hours ago






  • 2





    i dont think [0,4,2,1,3] is the answer, its the desired output structure, maybe, that s/he is looking for? 🤔

    – Emma
    3 hours ago








  • 2





    @ruakh sure. I'm guessing its an open ended question. Can you make an assumption and come up with a possible outcome?

    – SFer
    2 hours ago






  • 2





    I'm not sure if I want to have dinner with these folks, not if my first two "friends" don't like me back!

    – Scott Sauyet
    2 hours ago
















  • 1





    You are row and column 0, you like all your friends, but only your friends 2 and 3 like you, "friends" 1 and 2 dislike you (-1 in column 0 - that's your own popularity). The expample means the sitting order: You, next to you friend 4, then 2, 1, 3 which is on the other side next to you.

    – Quasimodo's clone
    3 hours ago








  • 2





    The problem statement seems too vague; if the goal is that "as many people as possible are seated next to people they consider friends and not enemies", how do we quantify that? For example: suppose that one arrangement has each guest adjacent to one person they like and one person they hate, and a different arrangement has each guest adjacent to two people they're neutral about. Which of these is considered better?

    – ruakh
    3 hours ago






  • 2





    i dont think [0,4,2,1,3] is the answer, its the desired output structure, maybe, that s/he is looking for? 🤔

    – Emma
    3 hours ago








  • 2





    @ruakh sure. I'm guessing its an open ended question. Can you make an assumption and come up with a possible outcome?

    – SFer
    2 hours ago






  • 2





    I'm not sure if I want to have dinner with these folks, not if my first two "friends" don't like me back!

    – Scott Sauyet
    2 hours ago










1




1





You are row and column 0, you like all your friends, but only your friends 2 and 3 like you, "friends" 1 and 2 dislike you (-1 in column 0 - that's your own popularity). The expample means the sitting order: You, next to you friend 4, then 2, 1, 3 which is on the other side next to you.

– Quasimodo's clone
3 hours ago







You are row and column 0, you like all your friends, but only your friends 2 and 3 like you, "friends" 1 and 2 dislike you (-1 in column 0 - that's your own popularity). The expample means the sitting order: You, next to you friend 4, then 2, 1, 3 which is on the other side next to you.

– Quasimodo's clone
3 hours ago






2




2





The problem statement seems too vague; if the goal is that "as many people as possible are seated next to people they consider friends and not enemies", how do we quantify that? For example: suppose that one arrangement has each guest adjacent to one person they like and one person they hate, and a different arrangement has each guest adjacent to two people they're neutral about. Which of these is considered better?

– ruakh
3 hours ago





The problem statement seems too vague; if the goal is that "as many people as possible are seated next to people they consider friends and not enemies", how do we quantify that? For example: suppose that one arrangement has each guest adjacent to one person they like and one person they hate, and a different arrangement has each guest adjacent to two people they're neutral about. Which of these is considered better?

– ruakh
3 hours ago




2




2





i dont think [0,4,2,1,3] is the answer, its the desired output structure, maybe, that s/he is looking for? 🤔

– Emma
3 hours ago







i dont think [0,4,2,1,3] is the answer, its the desired output structure, maybe, that s/he is looking for? 🤔

– Emma
3 hours ago






2




2





@ruakh sure. I'm guessing its an open ended question. Can you make an assumption and come up with a possible outcome?

– SFer
2 hours ago





@ruakh sure. I'm guessing its an open ended question. Can you make an assumption and come up with a possible outcome?

– SFer
2 hours ago




2




2





I'm not sure if I want to have dinner with these folks, not if my first two "friends" don't like me back!

– Scott Sauyet
2 hours ago







I'm not sure if I want to have dinner with these folks, not if my first two "friends" don't like me back!

– Scott Sauyet
2 hours ago














2 Answers
2






active

oldest

votes


















3















How did he/she come up with [0,4,2,1,3]?




That permutation certainly isn't the right answer for the example input (see reasoning below), so I think that Emma's comment above is spot-on: the problem statement is just demonstrating what a "seating arrangement as an Array" should look like in general, not specifically demonstrating the optimal seating arrangement for the example input.





As for why I say that [0,4,2,1,3] certainly isn't the right answer for the example you've given . . . I don't completely understand how we decide whether one permutation is better than another, but it's clear that [0,4,1,2,3] is better by any measure. For both [0,4,2,1,3] and [0,4,1,2,3], the first person (0) likes both neighbors; the second person (4) is neutral toward both neighbors; and the third and fifth people (2 and 3 in the former, 1 and 3 in the latter) each like one neighbor and are neutral toward the other. The only difference between the two permutations is that in [0,4,2,1,3], the fourth person (1) is neutral toward one neighbor and dislikes the other, whereas in [0,4,1,2,3], the fourth person (2) is neutral toward one neighbor and likes the other. So the latter is obviously superior, no matter whether we consider it more important to increase likes or to decrease dislikes.






share|improve this answer
























  • OMG! thanks a million for tagging my profile in your answer! 💙💙💙, To be honest, i had no idea, saw the e.g. behind [0,4,2,1,3], then i realized that might not be the answer. 😄

    – Emma
    39 mins ago








  • 1





    @Emma Becoming a star can be so easy. ;-)

    – Quasimodo's clone
    20 mins ago











  • @Quasimodo'sclone 😍😍💙💙💙

    – Emma
    13 mins ago



















1














Checking all possible orders is a classical permutation task even if there might be a more efficient algorithm for this specific problem.



One optimization can be done by reducing the permutation to array length-1 since in circular orders e.g. 0,1,2,3,4 and 4,0,1,2,3 (and all further rotations) are the same. You can view the order from you own seat always starting at position 0.



(function ()
{
'use strict';

let popularity =
[
[ 0, 1, 1, 1, 1], // ← yes you like all your friends
[-1, 0, 1,-1, 0],
[-1, 1, 0, 1, 0],
[ 1, 1, 1, 0,-1],
[ 1, 0, 0,-1, 0],
];

function permutation(arr)
{
let
l = arr.length,
perms =
;

if(l<2)
return [arr];

for(let i=0; i<l; i++)
{
let
cpy = Array.from(arr),
[perm] = cpy.splice(i, 1)
;
perms.push(...permutation(cpy).map(v => [perm, ...v]));
}

return perms;
}


let
keys = Array.from(popularity.keys()).slice(1),
permutations = permutation(keys),
rating = permutations.map(v =>
{
let
last = v.length -1,

// start with our own relationships to the left and right neighbour
// (each: we like him, he likes us)
rate =
popularity [0] [v[0]]
+ popularity [v[0]] [0]
+ popularity [0] [v[last]]
+ popularity [v[last]] [0]
;

for(let i = 0; i<last; i++)
rate += popularity[v[i]][v[i+1]] + popularity[v[i+1]][v[i]];

return [rate, [0, ...v]];
}
).sort( (v1, v2) => ( v1[0] === v2[0] ? 0 : (v1[0] > v2[0] ? -1 : 1)) );

console.log(rating);

})();


output:



[ [ 8, [ 0, 4, 1, 2, 3 ] ],
[ 8, [ 0, 3, 2, 1, 4 ] ],
[ 6, [ 0, 3, 1, 2, 4 ] ],
[ 6, [ 0, 4, 2, 1, 3 ] ],
[ 4, [ 0, 1, 4, 2, 3 ] ],
[ 4, [ 0, 1, 2, 3, 4 ] ],
[ 4, [ 0, 4, 1, 3, 2 ] ],
[ 4, [ 0, 1, 3, 2, 4 ] ],
[ 4, [ 0, 2, 3, 1, 4 ] ],
[ 4, [ 0, 3, 2, 4, 1 ] ],
[ 4, [ 0, 4, 2, 3, 1 ] ],
[ 4, [ 0, 4, 3, 2, 1 ] ],
[ 2, [ 0, 3, 4, 2, 1 ] ],
[ 2, [ 0, 3, 1, 4, 2 ] ],
[ 2, [ 0, 2, 4, 1, 3 ] ],
[ 2, [ 0, 4, 3, 1, 2 ] ],
[ 2, [ 0, 3, 4, 1, 2 ] ],
[ 2, [ 0, 1, 2, 4, 3 ] ],
[ 2, [ 0, 2, 1, 4, 3 ] ],
[ 2, [ 0, 2, 1, 3, 4 ] ],
[ 0, [ 0, 1, 4, 3, 2 ] ],
[ 0, [ 0, 2, 3, 4, 1 ] ],
[ -2, [ 0, 1, 3, 4, 2 ] ],
[ -2, [ 0, 2, 4, 3, 1 ] ] ]


As we can see, there still are reversed permutations combined with yourself (0) having the same rating of course. Eleminating mirrored orders, i.e. reversed permutations, would be another optimization.



I did this for demonstration in single steps to have a more readable code facing single problems step by step. You could refactor the rating calculation directly into the permutation algorithm.



A permutation has an O(N!) complexity. Since we ignore our own seat, the permutation part is reduced to O((N-1)!).






share|improve this answer





















  • 1





    @Quasimodos impressive! 💙💙💙

    – Emma
    38 mins ago











Your Answer






StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});






SFer is a new contributor. Be nice, and check out our Code of Conduct.










draft saved

draft discarded


















StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f54508726%2fissues-with-understanding-dining-table-optimal-seating-algorithm%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown

























2 Answers
2






active

oldest

votes








2 Answers
2






active

oldest

votes









active

oldest

votes






active

oldest

votes









3















How did he/she come up with [0,4,2,1,3]?




That permutation certainly isn't the right answer for the example input (see reasoning below), so I think that Emma's comment above is spot-on: the problem statement is just demonstrating what a "seating arrangement as an Array" should look like in general, not specifically demonstrating the optimal seating arrangement for the example input.





As for why I say that [0,4,2,1,3] certainly isn't the right answer for the example you've given . . . I don't completely understand how we decide whether one permutation is better than another, but it's clear that [0,4,1,2,3] is better by any measure. For both [0,4,2,1,3] and [0,4,1,2,3], the first person (0) likes both neighbors; the second person (4) is neutral toward both neighbors; and the third and fifth people (2 and 3 in the former, 1 and 3 in the latter) each like one neighbor and are neutral toward the other. The only difference between the two permutations is that in [0,4,2,1,3], the fourth person (1) is neutral toward one neighbor and dislikes the other, whereas in [0,4,1,2,3], the fourth person (2) is neutral toward one neighbor and likes the other. So the latter is obviously superior, no matter whether we consider it more important to increase likes or to decrease dislikes.






share|improve this answer
























  • OMG! thanks a million for tagging my profile in your answer! 💙💙💙, To be honest, i had no idea, saw the e.g. behind [0,4,2,1,3], then i realized that might not be the answer. 😄

    – Emma
    39 mins ago








  • 1





    @Emma Becoming a star can be so easy. ;-)

    – Quasimodo's clone
    20 mins ago











  • @Quasimodo'sclone 😍😍💙💙💙

    – Emma
    13 mins ago
















3















How did he/she come up with [0,4,2,1,3]?




That permutation certainly isn't the right answer for the example input (see reasoning below), so I think that Emma's comment above is spot-on: the problem statement is just demonstrating what a "seating arrangement as an Array" should look like in general, not specifically demonstrating the optimal seating arrangement for the example input.





As for why I say that [0,4,2,1,3] certainly isn't the right answer for the example you've given . . . I don't completely understand how we decide whether one permutation is better than another, but it's clear that [0,4,1,2,3] is better by any measure. For both [0,4,2,1,3] and [0,4,1,2,3], the first person (0) likes both neighbors; the second person (4) is neutral toward both neighbors; and the third and fifth people (2 and 3 in the former, 1 and 3 in the latter) each like one neighbor and are neutral toward the other. The only difference between the two permutations is that in [0,4,2,1,3], the fourth person (1) is neutral toward one neighbor and dislikes the other, whereas in [0,4,1,2,3], the fourth person (2) is neutral toward one neighbor and likes the other. So the latter is obviously superior, no matter whether we consider it more important to increase likes or to decrease dislikes.






share|improve this answer
























  • OMG! thanks a million for tagging my profile in your answer! 💙💙💙, To be honest, i had no idea, saw the e.g. behind [0,4,2,1,3], then i realized that might not be the answer. 😄

    – Emma
    39 mins ago








  • 1





    @Emma Becoming a star can be so easy. ;-)

    – Quasimodo's clone
    20 mins ago











  • @Quasimodo'sclone 😍😍💙💙💙

    – Emma
    13 mins ago














3












3








3








How did he/she come up with [0,4,2,1,3]?




That permutation certainly isn't the right answer for the example input (see reasoning below), so I think that Emma's comment above is spot-on: the problem statement is just demonstrating what a "seating arrangement as an Array" should look like in general, not specifically demonstrating the optimal seating arrangement for the example input.





As for why I say that [0,4,2,1,3] certainly isn't the right answer for the example you've given . . . I don't completely understand how we decide whether one permutation is better than another, but it's clear that [0,4,1,2,3] is better by any measure. For both [0,4,2,1,3] and [0,4,1,2,3], the first person (0) likes both neighbors; the second person (4) is neutral toward both neighbors; and the third and fifth people (2 and 3 in the former, 1 and 3 in the latter) each like one neighbor and are neutral toward the other. The only difference between the two permutations is that in [0,4,2,1,3], the fourth person (1) is neutral toward one neighbor and dislikes the other, whereas in [0,4,1,2,3], the fourth person (2) is neutral toward one neighbor and likes the other. So the latter is obviously superior, no matter whether we consider it more important to increase likes or to decrease dislikes.






share|improve this answer














How did he/she come up with [0,4,2,1,3]?




That permutation certainly isn't the right answer for the example input (see reasoning below), so I think that Emma's comment above is spot-on: the problem statement is just demonstrating what a "seating arrangement as an Array" should look like in general, not specifically demonstrating the optimal seating arrangement for the example input.





As for why I say that [0,4,2,1,3] certainly isn't the right answer for the example you've given . . . I don't completely understand how we decide whether one permutation is better than another, but it's clear that [0,4,1,2,3] is better by any measure. For both [0,4,2,1,3] and [0,4,1,2,3], the first person (0) likes both neighbors; the second person (4) is neutral toward both neighbors; and the third and fifth people (2 and 3 in the former, 1 and 3 in the latter) each like one neighbor and are neutral toward the other. The only difference between the two permutations is that in [0,4,2,1,3], the fourth person (1) is neutral toward one neighbor and dislikes the other, whereas in [0,4,1,2,3], the fourth person (2) is neutral toward one neighbor and likes the other. So the latter is obviously superior, no matter whether we consider it more important to increase likes or to decrease dislikes.







share|improve this answer












share|improve this answer



share|improve this answer










answered 1 hour ago









ruakhruakh

125k13200253




125k13200253













  • OMG! thanks a million for tagging my profile in your answer! 💙💙💙, To be honest, i had no idea, saw the e.g. behind [0,4,2,1,3], then i realized that might not be the answer. 😄

    – Emma
    39 mins ago








  • 1





    @Emma Becoming a star can be so easy. ;-)

    – Quasimodo's clone
    20 mins ago











  • @Quasimodo'sclone 😍😍💙💙💙

    – Emma
    13 mins ago



















  • OMG! thanks a million for tagging my profile in your answer! 💙💙💙, To be honest, i had no idea, saw the e.g. behind [0,4,2,1,3], then i realized that might not be the answer. 😄

    – Emma
    39 mins ago








  • 1





    @Emma Becoming a star can be so easy. ;-)

    – Quasimodo's clone
    20 mins ago











  • @Quasimodo'sclone 😍😍💙💙💙

    – Emma
    13 mins ago

















OMG! thanks a million for tagging my profile in your answer! 💙💙💙, To be honest, i had no idea, saw the e.g. behind [0,4,2,1,3], then i realized that might not be the answer. 😄

– Emma
39 mins ago







OMG! thanks a million for tagging my profile in your answer! 💙💙💙, To be honest, i had no idea, saw the e.g. behind [0,4,2,1,3], then i realized that might not be the answer. 😄

– Emma
39 mins ago






1




1





@Emma Becoming a star can be so easy. ;-)

– Quasimodo's clone
20 mins ago





@Emma Becoming a star can be so easy. ;-)

– Quasimodo's clone
20 mins ago













@Quasimodo'sclone 😍😍💙💙💙

– Emma
13 mins ago





@Quasimodo'sclone 😍😍💙💙💙

– Emma
13 mins ago













1














Checking all possible orders is a classical permutation task even if there might be a more efficient algorithm for this specific problem.



One optimization can be done by reducing the permutation to array length-1 since in circular orders e.g. 0,1,2,3,4 and 4,0,1,2,3 (and all further rotations) are the same. You can view the order from you own seat always starting at position 0.



(function ()
{
'use strict';

let popularity =
[
[ 0, 1, 1, 1, 1], // ← yes you like all your friends
[-1, 0, 1,-1, 0],
[-1, 1, 0, 1, 0],
[ 1, 1, 1, 0,-1],
[ 1, 0, 0,-1, 0],
];

function permutation(arr)
{
let
l = arr.length,
perms =
;

if(l<2)
return [arr];

for(let i=0; i<l; i++)
{
let
cpy = Array.from(arr),
[perm] = cpy.splice(i, 1)
;
perms.push(...permutation(cpy).map(v => [perm, ...v]));
}

return perms;
}


let
keys = Array.from(popularity.keys()).slice(1),
permutations = permutation(keys),
rating = permutations.map(v =>
{
let
last = v.length -1,

// start with our own relationships to the left and right neighbour
// (each: we like him, he likes us)
rate =
popularity [0] [v[0]]
+ popularity [v[0]] [0]
+ popularity [0] [v[last]]
+ popularity [v[last]] [0]
;

for(let i = 0; i<last; i++)
rate += popularity[v[i]][v[i+1]] + popularity[v[i+1]][v[i]];

return [rate, [0, ...v]];
}
).sort( (v1, v2) => ( v1[0] === v2[0] ? 0 : (v1[0] > v2[0] ? -1 : 1)) );

console.log(rating);

})();


output:



[ [ 8, [ 0, 4, 1, 2, 3 ] ],
[ 8, [ 0, 3, 2, 1, 4 ] ],
[ 6, [ 0, 3, 1, 2, 4 ] ],
[ 6, [ 0, 4, 2, 1, 3 ] ],
[ 4, [ 0, 1, 4, 2, 3 ] ],
[ 4, [ 0, 1, 2, 3, 4 ] ],
[ 4, [ 0, 4, 1, 3, 2 ] ],
[ 4, [ 0, 1, 3, 2, 4 ] ],
[ 4, [ 0, 2, 3, 1, 4 ] ],
[ 4, [ 0, 3, 2, 4, 1 ] ],
[ 4, [ 0, 4, 2, 3, 1 ] ],
[ 4, [ 0, 4, 3, 2, 1 ] ],
[ 2, [ 0, 3, 4, 2, 1 ] ],
[ 2, [ 0, 3, 1, 4, 2 ] ],
[ 2, [ 0, 2, 4, 1, 3 ] ],
[ 2, [ 0, 4, 3, 1, 2 ] ],
[ 2, [ 0, 3, 4, 1, 2 ] ],
[ 2, [ 0, 1, 2, 4, 3 ] ],
[ 2, [ 0, 2, 1, 4, 3 ] ],
[ 2, [ 0, 2, 1, 3, 4 ] ],
[ 0, [ 0, 1, 4, 3, 2 ] ],
[ 0, [ 0, 2, 3, 4, 1 ] ],
[ -2, [ 0, 1, 3, 4, 2 ] ],
[ -2, [ 0, 2, 4, 3, 1 ] ] ]


As we can see, there still are reversed permutations combined with yourself (0) having the same rating of course. Eleminating mirrored orders, i.e. reversed permutations, would be another optimization.



I did this for demonstration in single steps to have a more readable code facing single problems step by step. You could refactor the rating calculation directly into the permutation algorithm.



A permutation has an O(N!) complexity. Since we ignore our own seat, the permutation part is reduced to O((N-1)!).






share|improve this answer





















  • 1





    @Quasimodos impressive! 💙💙💙

    – Emma
    38 mins ago
















1














Checking all possible orders is a classical permutation task even if there might be a more efficient algorithm for this specific problem.



One optimization can be done by reducing the permutation to array length-1 since in circular orders e.g. 0,1,2,3,4 and 4,0,1,2,3 (and all further rotations) are the same. You can view the order from you own seat always starting at position 0.



(function ()
{
'use strict';

let popularity =
[
[ 0, 1, 1, 1, 1], // ← yes you like all your friends
[-1, 0, 1,-1, 0],
[-1, 1, 0, 1, 0],
[ 1, 1, 1, 0,-1],
[ 1, 0, 0,-1, 0],
];

function permutation(arr)
{
let
l = arr.length,
perms =
;

if(l<2)
return [arr];

for(let i=0; i<l; i++)
{
let
cpy = Array.from(arr),
[perm] = cpy.splice(i, 1)
;
perms.push(...permutation(cpy).map(v => [perm, ...v]));
}

return perms;
}


let
keys = Array.from(popularity.keys()).slice(1),
permutations = permutation(keys),
rating = permutations.map(v =>
{
let
last = v.length -1,

// start with our own relationships to the left and right neighbour
// (each: we like him, he likes us)
rate =
popularity [0] [v[0]]
+ popularity [v[0]] [0]
+ popularity [0] [v[last]]
+ popularity [v[last]] [0]
;

for(let i = 0; i<last; i++)
rate += popularity[v[i]][v[i+1]] + popularity[v[i+1]][v[i]];

return [rate, [0, ...v]];
}
).sort( (v1, v2) => ( v1[0] === v2[0] ? 0 : (v1[0] > v2[0] ? -1 : 1)) );

console.log(rating);

})();


output:



[ [ 8, [ 0, 4, 1, 2, 3 ] ],
[ 8, [ 0, 3, 2, 1, 4 ] ],
[ 6, [ 0, 3, 1, 2, 4 ] ],
[ 6, [ 0, 4, 2, 1, 3 ] ],
[ 4, [ 0, 1, 4, 2, 3 ] ],
[ 4, [ 0, 1, 2, 3, 4 ] ],
[ 4, [ 0, 4, 1, 3, 2 ] ],
[ 4, [ 0, 1, 3, 2, 4 ] ],
[ 4, [ 0, 2, 3, 1, 4 ] ],
[ 4, [ 0, 3, 2, 4, 1 ] ],
[ 4, [ 0, 4, 2, 3, 1 ] ],
[ 4, [ 0, 4, 3, 2, 1 ] ],
[ 2, [ 0, 3, 4, 2, 1 ] ],
[ 2, [ 0, 3, 1, 4, 2 ] ],
[ 2, [ 0, 2, 4, 1, 3 ] ],
[ 2, [ 0, 4, 3, 1, 2 ] ],
[ 2, [ 0, 3, 4, 1, 2 ] ],
[ 2, [ 0, 1, 2, 4, 3 ] ],
[ 2, [ 0, 2, 1, 4, 3 ] ],
[ 2, [ 0, 2, 1, 3, 4 ] ],
[ 0, [ 0, 1, 4, 3, 2 ] ],
[ 0, [ 0, 2, 3, 4, 1 ] ],
[ -2, [ 0, 1, 3, 4, 2 ] ],
[ -2, [ 0, 2, 4, 3, 1 ] ] ]


As we can see, there still are reversed permutations combined with yourself (0) having the same rating of course. Eleminating mirrored orders, i.e. reversed permutations, would be another optimization.



I did this for demonstration in single steps to have a more readable code facing single problems step by step. You could refactor the rating calculation directly into the permutation algorithm.



A permutation has an O(N!) complexity. Since we ignore our own seat, the permutation part is reduced to O((N-1)!).






share|improve this answer





















  • 1





    @Quasimodos impressive! 💙💙💙

    – Emma
    38 mins ago














1












1








1







Checking all possible orders is a classical permutation task even if there might be a more efficient algorithm for this specific problem.



One optimization can be done by reducing the permutation to array length-1 since in circular orders e.g. 0,1,2,3,4 and 4,0,1,2,3 (and all further rotations) are the same. You can view the order from you own seat always starting at position 0.



(function ()
{
'use strict';

let popularity =
[
[ 0, 1, 1, 1, 1], // ← yes you like all your friends
[-1, 0, 1,-1, 0],
[-1, 1, 0, 1, 0],
[ 1, 1, 1, 0,-1],
[ 1, 0, 0,-1, 0],
];

function permutation(arr)
{
let
l = arr.length,
perms =
;

if(l<2)
return [arr];

for(let i=0; i<l; i++)
{
let
cpy = Array.from(arr),
[perm] = cpy.splice(i, 1)
;
perms.push(...permutation(cpy).map(v => [perm, ...v]));
}

return perms;
}


let
keys = Array.from(popularity.keys()).slice(1),
permutations = permutation(keys),
rating = permutations.map(v =>
{
let
last = v.length -1,

// start with our own relationships to the left and right neighbour
// (each: we like him, he likes us)
rate =
popularity [0] [v[0]]
+ popularity [v[0]] [0]
+ popularity [0] [v[last]]
+ popularity [v[last]] [0]
;

for(let i = 0; i<last; i++)
rate += popularity[v[i]][v[i+1]] + popularity[v[i+1]][v[i]];

return [rate, [0, ...v]];
}
).sort( (v1, v2) => ( v1[0] === v2[0] ? 0 : (v1[0] > v2[0] ? -1 : 1)) );

console.log(rating);

})();


output:



[ [ 8, [ 0, 4, 1, 2, 3 ] ],
[ 8, [ 0, 3, 2, 1, 4 ] ],
[ 6, [ 0, 3, 1, 2, 4 ] ],
[ 6, [ 0, 4, 2, 1, 3 ] ],
[ 4, [ 0, 1, 4, 2, 3 ] ],
[ 4, [ 0, 1, 2, 3, 4 ] ],
[ 4, [ 0, 4, 1, 3, 2 ] ],
[ 4, [ 0, 1, 3, 2, 4 ] ],
[ 4, [ 0, 2, 3, 1, 4 ] ],
[ 4, [ 0, 3, 2, 4, 1 ] ],
[ 4, [ 0, 4, 2, 3, 1 ] ],
[ 4, [ 0, 4, 3, 2, 1 ] ],
[ 2, [ 0, 3, 4, 2, 1 ] ],
[ 2, [ 0, 3, 1, 4, 2 ] ],
[ 2, [ 0, 2, 4, 1, 3 ] ],
[ 2, [ 0, 4, 3, 1, 2 ] ],
[ 2, [ 0, 3, 4, 1, 2 ] ],
[ 2, [ 0, 1, 2, 4, 3 ] ],
[ 2, [ 0, 2, 1, 4, 3 ] ],
[ 2, [ 0, 2, 1, 3, 4 ] ],
[ 0, [ 0, 1, 4, 3, 2 ] ],
[ 0, [ 0, 2, 3, 4, 1 ] ],
[ -2, [ 0, 1, 3, 4, 2 ] ],
[ -2, [ 0, 2, 4, 3, 1 ] ] ]


As we can see, there still are reversed permutations combined with yourself (0) having the same rating of course. Eleminating mirrored orders, i.e. reversed permutations, would be another optimization.



I did this for demonstration in single steps to have a more readable code facing single problems step by step. You could refactor the rating calculation directly into the permutation algorithm.



A permutation has an O(N!) complexity. Since we ignore our own seat, the permutation part is reduced to O((N-1)!).






share|improve this answer















Checking all possible orders is a classical permutation task even if there might be a more efficient algorithm for this specific problem.



One optimization can be done by reducing the permutation to array length-1 since in circular orders e.g. 0,1,2,3,4 and 4,0,1,2,3 (and all further rotations) are the same. You can view the order from you own seat always starting at position 0.



(function ()
{
'use strict';

let popularity =
[
[ 0, 1, 1, 1, 1], // ← yes you like all your friends
[-1, 0, 1,-1, 0],
[-1, 1, 0, 1, 0],
[ 1, 1, 1, 0,-1],
[ 1, 0, 0,-1, 0],
];

function permutation(arr)
{
let
l = arr.length,
perms =
;

if(l<2)
return [arr];

for(let i=0; i<l; i++)
{
let
cpy = Array.from(arr),
[perm] = cpy.splice(i, 1)
;
perms.push(...permutation(cpy).map(v => [perm, ...v]));
}

return perms;
}


let
keys = Array.from(popularity.keys()).slice(1),
permutations = permutation(keys),
rating = permutations.map(v =>
{
let
last = v.length -1,

// start with our own relationships to the left and right neighbour
// (each: we like him, he likes us)
rate =
popularity [0] [v[0]]
+ popularity [v[0]] [0]
+ popularity [0] [v[last]]
+ popularity [v[last]] [0]
;

for(let i = 0; i<last; i++)
rate += popularity[v[i]][v[i+1]] + popularity[v[i+1]][v[i]];

return [rate, [0, ...v]];
}
).sort( (v1, v2) => ( v1[0] === v2[0] ? 0 : (v1[0] > v2[0] ? -1 : 1)) );

console.log(rating);

})();


output:



[ [ 8, [ 0, 4, 1, 2, 3 ] ],
[ 8, [ 0, 3, 2, 1, 4 ] ],
[ 6, [ 0, 3, 1, 2, 4 ] ],
[ 6, [ 0, 4, 2, 1, 3 ] ],
[ 4, [ 0, 1, 4, 2, 3 ] ],
[ 4, [ 0, 1, 2, 3, 4 ] ],
[ 4, [ 0, 4, 1, 3, 2 ] ],
[ 4, [ 0, 1, 3, 2, 4 ] ],
[ 4, [ 0, 2, 3, 1, 4 ] ],
[ 4, [ 0, 3, 2, 4, 1 ] ],
[ 4, [ 0, 4, 2, 3, 1 ] ],
[ 4, [ 0, 4, 3, 2, 1 ] ],
[ 2, [ 0, 3, 4, 2, 1 ] ],
[ 2, [ 0, 3, 1, 4, 2 ] ],
[ 2, [ 0, 2, 4, 1, 3 ] ],
[ 2, [ 0, 4, 3, 1, 2 ] ],
[ 2, [ 0, 3, 4, 1, 2 ] ],
[ 2, [ 0, 1, 2, 4, 3 ] ],
[ 2, [ 0, 2, 1, 4, 3 ] ],
[ 2, [ 0, 2, 1, 3, 4 ] ],
[ 0, [ 0, 1, 4, 3, 2 ] ],
[ 0, [ 0, 2, 3, 4, 1 ] ],
[ -2, [ 0, 1, 3, 4, 2 ] ],
[ -2, [ 0, 2, 4, 3, 1 ] ] ]


As we can see, there still are reversed permutations combined with yourself (0) having the same rating of course. Eleminating mirrored orders, i.e. reversed permutations, would be another optimization.



I did this for demonstration in single steps to have a more readable code facing single problems step by step. You could refactor the rating calculation directly into the permutation algorithm.



A permutation has an O(N!) complexity. Since we ignore our own seat, the permutation part is reduced to O((N-1)!).







share|improve this answer














share|improve this answer



share|improve this answer








edited 33 mins ago

























answered 1 hour ago









Quasimodo's cloneQuasimodo's clone

3,79611029




3,79611029








  • 1





    @Quasimodos impressive! 💙💙💙

    – Emma
    38 mins ago














  • 1





    @Quasimodos impressive! 💙💙💙

    – Emma
    38 mins ago








1




1





@Quasimodos impressive! 💙💙💙

– Emma
38 mins ago





@Quasimodos impressive! 💙💙💙

– Emma
38 mins ago










SFer is a new contributor. Be nice, and check out our Code of Conduct.










draft saved

draft discarded


















SFer is a new contributor. Be nice, and check out our Code of Conduct.













SFer is a new contributor. Be nice, and check out our Code of Conduct.












SFer is a new contributor. Be nice, and check out our Code of Conduct.
















Thanks for contributing an answer to Stack Overflow!


  • Please be sure to answer the question. Provide details and share your research!

But avoid



  • Asking for help, clarification, or responding to other answers.

  • Making statements based on opinion; back them up with references or personal experience.


To learn more, see our tips on writing great answers.




draft saved


draft discarded














StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f54508726%2fissues-with-understanding-dining-table-optimal-seating-algorithm%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown





















































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown

































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown







Popular posts from this blog

A CLEAN and SIMPLE way to add appendices to Table of Contents and bookmarks

Calculate evaluation metrics using cross_val_predict sklearn

Insert data from modal to MySQL (multiple modal on website)