Bienvenue sur le forum !

Si vous souhaitez rejoindre la communauté, cliquez sur l'un de ces boutons !

Qt 5 : 5.9.1 - Qt Creator : 4.4.0 - Qt Installer : 2.0.3 - JOM : 1.1.2 - Qt Build suite : 1.7.0 - VS Qt 5 : 2.0.0

[Algorithme] Génération de couples "optimisé" sans répétition

Hello,

Voici un petit algo sur lequel j'ai planché avec des collègues par rapport à un projet. Si ça peut servir à d'autres...
L'objectif est de générer des couples d'équipes pour former des matchs afin que toutes les équipes se rencontrent entre elles, mais sans qu'une même équipe ne joue deux fois (ou plus) d'affilé. Il fonctionne et est fiable à partir de 5 équipes*, mais il n'a pas non plus été testé intensivement...

*Lorsque le nombre de matchs possibles atteint au moins deux fois le nombre d'équipes.

Voici l'algo en C++ 11 "templaté":
template <typename T>
std::tuple<T,T> createTupleCouple(const T &e1, const T &e2)
{
return std::tuple<T,T>(e1,e2);
}


// Generate couples (list of tuples) from a list of element.
// Result is garanteed without successive elements for 5 and more elements, assuming a set without duplicates.
// No successiveness is not garanteed when the possible number of couples is less than 2 times the list size (4 and less).

// C is the couple type created by the function/functor createC of type CreateCouple
template <typename C, template <typename> class Container, typename T,
typename CreateCouple = C(const T &, const T &)>
std::vector< C > generateCouples(const Container<T> &list, CreateCouple createC = createTupleCouple)
{
std::vector< C > generatedCouples;

const int listSize { list.size() };
const bool isListEven { (listSize%2 == 0) };
const int numberOfCouplesToFind { (listSize-1)*listSize / 2 }; // = 1+2+3+...+'size'

generatedCouples.reserve(listSize);

int index { 0 }; // Index used to loop through the list

#define COUPLE_INDEXES(list, listSize, index, gap) list.at(index % listSize), list.at((index+1+gap) % listSize)

// First part: find all adjacent couples by looping the list twice
// If the list is even, we need to skip the first element when i reaches the middle of the list.
for (int i {0}; i < listSize; ++i) {
const C couple { createC( COUPLE_INDEXES(list, listSize, index, 0) ) };
generatedCouples.push_back(couple);

index += 2;
if (isListEven && (i == (listSize/2+1))) {
// Skip first element by incrementing index
index++;
}
}


// Second part: find all next couples
// Couples are formed with the elements at index 'i' and 'i+1+gap'
// 'gap' is incremented after each stage. There are 'size/2' stages,
// and for each stage 'size-2-stage number' couples must be found.
// 'stage number' ranges from 0 to 'size/2', and is incremented when
// the required number of couples for the current stage is reached.

int gap { 1 }; // Gap, increased after each stage

// Stages: first 'size-2' couples, then each stage has one less couples until it reaches 2 and should stop.
int stageSize { listSize-2 };
int stageCounter { 0 }; // Number of couples found for the current stage

for (int i {0}; i < (numberOfCouplesToFind-listSize); ++i) {
const C couple { createC( COUPLE_INDEXES(list, listSize, index, gap) ) };
generatedCouples.push_back(couple);

index++;
stageCounter++;

// Check end of current stage
if (stageCounter == stageSize) {
stageSize--;
stageCounter = 0;
gap++;

// Need to reset index to 0 if list size is odd
if (!isListEven) index = 0;
}
}

#undef COUPLE_INDEXES

return generatedCouples;
}
L'utilisation est très simple :
int main()
{
// Fancy team names!
const QList<QString> teams { "A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N" };

const auto teamSize = teams.size();
const auto numberOfCouples = (teamSize-1)*teamSize / 2;

qDebug() << "Teams: (" << numberOfCouples << ")\n" << teams;

auto couples = generateCouples< std::tuple<QString,QString> >(teams);

// Print couples
qDebug("\nCouples: ");
for (const auto couple : couples) {
qDebug() << std::get<0>(couple) << std::get<1>(couple);
}

return 0;
}
Du fait du template, normalement il gère n'importe quelle liste "compatible std", ou qui propose les méthodes size() et at().

CreateCouple est une fonction libre ou un "functor" qui retourne un "objet match" (ici un tuple pour createTupleCouple, mais ça peut être autre chose tant que la signature est compatible) en fonction des deux paramètres (deux équipes). Le type de cet objet est à préciser lors de l'appel de generateCouples, j'aurais bien aimé arriver à l'enlever, mais je ne vois pas comment faire.

Ci-joint un projet Qt zippé et le code Python de base qui lui intègre aussi la vérification de la liste générée (fichier txt à renommer en .py).

! L'algo n'a pas été testé intensivement, mais aucune erreur n'a été rapportée jusqu'ici !
zip
zip
MatchSequencer.zip
2K
txt
txt
TeamsSequencer.txt
4K

Réponses

Connectez-vous ou Inscrivez-vous pour répondre.