10 personnes à placer

[chan79]

On a une rangée de 10 chaises numérotées.
On doit y placer 5 Chinois, 3 Allemands et 2 Anglais.
Combien y a-t-il de façons de les placer (de leur attribuer un numéro) sachant qu'un Anglais et un Allemand ne peuvent pas être assis côte à côte ?
(à partir d'une disposition, si on permute par exemple deux Chinois, ça fait bien-sûr une disposition différente)

[LeJeu]

On a une rangée de 10 chaises numérotées.
On doit y placer 5 Chinois, 3 Allemands et 2 Anglais.
Combien y a-t-il de façons de les placer (de leur attribuer un numéro) sachant qu'un Anglais et un Allemand ne peuvent pas être assis côte à côte ?
(à partir d'une disposition, si on permute par exemple deux Chinois, ça fait bien-sûr une disposition différente)

je me propose de nous intéresser aux 2anglais, et en particulier aux nombres de places entre les deux, de regarder le nb de facon de placer alors les 3 allemands
on multipliera à la fin par 2!*3!*5! pour les permutations

1) les anglais sont cote à cote : 9 cas
->2 cas avec un anglais sur les bords qui laissent 7 places possibles pour les allemands
->7 cas avec les bords libres qui laissetn 6 places possibles pour le allemands
ce qui donne 2*(7*6*5) + 7*(6*5*4)

2) il y a une place entre les deux anglais : 8 cas
->2 cas avec un anglais sur les bords qui laissent 6 places
->6 cas avec les bords libres qui laissent 5 places dispos
ce qui donne 2*(6*5*4) + 6 (5*4*3)

3) deux places entre les deux anglais : 7 cas
-> 2 cas avec un anglais sur les bords qui laissent 5 places
-> 5 cas avec les bords libres qui laissent 4 places dispos
ce qui donne 2 ( 5*4*3) + 5 ( 4*3*2)

A partir de là une place va être possible entre les anglais
4) trois places entre les 2 anglais : 6 cas
-> 2 cas avec un anglais sur le bords qui laisse 5 places
-> 4 cas qui laissent les bords libres qui laissent 4 places dispos
ce qui donne 2 *(5*4*3) + 4 (4*3*2

idem pour 4 place, 5 places, 6 et 7 places
2 *(5*4*3) + 3 (4*3*2)
2 *(5*4*3) + 2(4*3*2)
2 *(5*4*3) + 1 (4*3*2)
2 *(5*4*3) + 0 (4*3*2)

pour terminer avec huit places entre les 2
(6*5*4 )

Reste à additionner tout ça ...






->

[chan79]

1) les anglais sont cote à cote : 9 cas
->2 cas avec un anglais sur les bords qui laissent 7 places possibles pour les allemands
->7 cas avec les bords libres qui laissent 6 places possibles pour le allemands
ce qui donne 2*(7*6*5) + 7*(6*5*4)
->

Salut LeJeu
Ca fait pas trop si tu multiplies à la fin par 2!3!5! ?

[fatal_error]

hello,

ca se résoud trivialement en brute force

Code: Tout sélectionner

#include
#include
#include

class Person{
public:
  Person(size_t id, const std::string& nationality):_id(id), _nationality(nationality){}
  bool operator& v){
  size_t len = v.size() - 1;
  for(size_t i=0; i& v){
  std::stringstream oss;
  for(const auto& p:v){
    oss v;
  size_t id=0;
  v.push_back(Person(id++, Person::chinese));
  v.push_back(Person(id++, Person::chinese));
  v.push_back(Person(id++, Person::chinese));
  v.push_back(Person(id++, Person::chinese));
  v.push_back(Person(id++, Person::chinese));
  v.push_back(Person(id++, Person::german));
  v.push_back(Person(id++, Person::german));
  v.push_back(Person(id++, Person::german));
  v.push_back(Person(id++, Person::english));
  v.push_back(Person(id++, Person::english));

  size_t count = 0;
  do {
    if(validateConfig(v)){
      count++;
    }
  } while ( std::next_permutation(v.begin(), v.end()) );

  std::cout
#include
#include
#include
#include
class Person{
public:
  Person(size_t id, const std::string& nationality):_id(id), _nationality(nationality){}
  bool operator Types;

protected:
  typedef std::map Container;
  Bag(const Container& map):_map(map){}
  Container _map;

public:
  Bag(const std::vector &v){
    for(const auto& person:v){
      _map[person.nationality()] = 0;
    }
    for(const auto& person:v){
      _map[person.nationality()]++;
    }
  }


  Types availableTypes(const Type& type)const{
    const auto& types = allTypes();
    if(type == Person::chinese){
      Types filteredTypes;
      for(const auto& t:types){
        if(countType(t)){
          filteredTypes.push_back(t);
        }
      }
      return filteredTypes;
    }

    if(type == Person::english){
      return excludeType(types, Person::german);
    }

    if(type == Person::german){
      return excludeType(types, Person::english);
    }

  }

  Types allTypes()const{
    Types v;
    for(const auto& pair:_map){
      v.push_back(pair.first);
    }
    return v;
  }

  Types excludeType(const Types &types, const Type &type)const{
    Types filteredTypes;
    for(const auto &t: types){
      if(t != type){
        if(countType(t)){
          filteredTypes.push_back(t);
        }
      }
    }
    return filteredTypes;
  }

  size_t countType(const Type& t)const{
    return _map.find(t)->second;
  }
  /*
    note: type is assumed to be removable from bag
  */
  Bag pick(const Type& type)const{
    Container map;
    Bag b(_map);
    b._map[type]--;
    return b;
  }
};

size_t fill(const Bag& bag, const Bag::Type& currentType, size_t depth){
  const auto& types = bag.availableTypes(currentType);
  //we reached the end
  if(types.empty()){
    return depth == 0;
  }
 
  size_t count = 0;
  for(const auto& type: types){
    const Bag &b = bag.pick(type);
    count += fill(b, type, depth-1);
  }
  return count;
}

size_t countPossibilities(const std::vector &v){
  Bag bag(v);
  size_t count = 0;
  const auto& types = bag.allTypes();
  for(const auto& type: types){
    const Bag &b = bag.pick(type);
    count += fill(b, type, v.size()-1);
  }
  return count;
};

size_t factorial(size_t i){
  size_t s = 1;
  for(size_t k=2;k v;
  size_t id=0;
  v.push_back(Person(id++, Person::chinese));
  v.push_back(Person(id++, Person::chinese));
  v.push_back(Person(id++, Person::chinese));
  v.push_back(Person(id++, Person::chinese));
  v.push_back(Person(id++, Person::chinese));
  v.push_back(Person(id++, Person::german));
  v.push_back(Person(id++, Person::german));
  v.push_back(Person(id++, Person::german));
  v.push_back(Person(id++, Person::english));
  v.push_back(Person(id++, Person::english));

  size_t factors = factorial(5)*factorial(3)*factorial(2);
  size_t count = countPossibilities(v);
  std::cout<<"final result : "<<(count*factors)<<std::endl;
  return 0;
}
//final result : 734400


ca se résoud aussi

[LeJeu]

Salut LeJeu
Ca fait pas trop si tu multiplies à la fin par 2!3!5! ?

Evidemment Le 3! est déjà pris en compte ....

Le 2!*5! devrait suffire....

[chan79]

OK avec le résultat de fatal
J'ai commencé à placer les Anglais, en distinguant selon le nombre de places interdites aux Allemands.
( les deux cas où les Anglais sont côte à côte à une extrémité, avec donc 1 place interdite)







Si on augmentait les nombres (par exemple 20 Anglais, 50 Allemands et 100 Chinois), il faudrait sans doute faire obligatoirement comme fatal.

[LeJeu]

hello,

ca se résoud trivialement en brute force

//final result : 734400

J'ai fait mon addition ....
2 *(7*6*5) + 10 ( 6*5*4) + 18 ( 5*4*3) + 15* ( 4*3*2= = 3060

et 3060 * 120*2 = 734 400

Fatal tu es une brute;-)

[LeJeu]

On est bien d'accord !

[chan79]

J'ai fait mon addition ....
2 *(7*6*5) + 10 ( 6*5*4) + 18 ( 5*4*3) + 15* ( 4*3*2) = 3060

et 3060 * 120*2 = 734 400

Fatal tu es une brute;-)

On est bien d'accord :zen:

[nodjim]

Fatal, ça se résout, ça ne résoud pas.

[fatal_error]

Si on augmentait les nombres (par exemple 20 Anglais, 50 Allemands et 100 Chinois), il faudrait sans doute faire obligatoirement comme fatal.

je pense pas, à mon avis mon algo termine pas (il prend déjà dans la seconde, vu que c'est factorielle, ca doit pas mal péter), faudrait y réfléchir un peu plus!

Fatal, ça se résout, ça ne résoud pas.

ah oui, c'est bon à savoir, thx. J'ai du la faire un paquet de fois :hum: