Διάταξη με επανάληψη

Στα μαθηματικά, μία διάταξη με επανάληψη μεγέθους  ενός συνόλου  με  στοιχεία είναι οποιαδήποτε -άδα , όπου  είναι στοιχεία του  (κάποια από τα οποία μπορεί να επαναλαμβάνονται πάνω από μία φορά).

Για παράδειγμα, για το σύνολο , οι δυνατές διατάξεις με επανάληψη ανά  είναι οι εξής:
, , , , 
, , , ,
, , , ,
, , , ,
Μερικές από τις δυνατές διατάξεις με επανάληψη μεγέθους  είναι οι εξής: ,  και .

Στις διατάξεις, τα στοιχεία της -άδας πρέπει να είναι όλα διαφορετικά μεταξύ τους, δηλαδή οι τριάδες  και  δεν είναι διατάξεις. Στους  συνδυασμούς  ανά , τα στοιχεία πρέπει πάλι να είναι διαφορετικά και η σειρά των στοιχείων της -άδας δεν έχει σημασία, δηλαδή  και  είναι ο ίδιος συνδυασμός.

 Πλήθος διατάξεων με επανάληψη 

Το πλήθος των διατάξεων  στοιχείων ανά  είναι .

 Παραδείγματα 

 Παράδειγμα 1ο 

Πόσοι τετραψήφιοι αριθμοί μπορούμε να σχηματίσουμε αν περιστρέψουμε τέσσερις φορές μία ρουλέτα με τα ψηφία 1 έως 9.

Απάντηση 

Υποθέτοντας ότι η ρουλέτα είναι δίκαιη, σε κάθε μία από τις τέσσερις περιστροφές έχουμε όλα τα στοιχεία του συνόλου «διαθέσιμα». Επομένως κάθε ψηφίο του τετραψήφιου αριθμού μπορεί να επιλεγεί με 9 διαφορετικούς τρόπους. Άρα το πλήθος των δυνατών τετραψήφιων αριθμών είναι το πλήθος των διατάξεων με επανάληψη 9 στοιχείων ανά 4, δηλαδή  πιθανοί τετραψήφιοι αριθμοί.

 Παράδειγμα 2ο 
Ένα μαγειρείο φτιάχνει ένα από τα εξής τρία γεύματα κάθε μέρα: μακαρόνια, κοτόπουλο ή ψάρι. Πόσα δυνατά εβδομαδιαία μενού μπορούν να προκύψουν;

Απάντηση

Κάθε ημέρα υπάρχουν τρία δυνατά γεύματα και υπάρχουν επτά ημέρες στην εβδομάδα. Επομένως, η απάντηση είναι το πλήθος των διατάξεων με επανάληψη 3 στοιχείων ανά 7, δηλαδή  δυνατά εβδομαδιαία μενού.

 Παραγωγή όλων των διατάξεων με επανάληψη 

Η παραγωγή όλων των διατάξεων με επανάληψη συνήθως γίνεται με την απαρίθμηση των αριθμών  έως  στο σύστημα αρίθμησης με βάση το . Κάθε ένα από τα  ψηφία του αριθμού μας δίνει την τιμή του στοιχείου. 

Στο αρχικό παράδειγμα, θα διατρέξουμε τους αριθμούς από το  έως το  στο σύστημα αρίθμησης με βάση το  και θα χρησιμοποιήσουμε την εξής αντιστοίχηση:
.
Επομένως, ο αριθμός 6 είναι το  στο τετραδικό σύστημα αρίθμησης (καθώς ) και αντιστοιχεί στην διάταξη με επανάληψη .

Ο παρακάτω κώδικας σε C++ δίνει όλους τους δυνατούς συνδυασμούς με επαναλήψεις για έναν δοσμένο πίνακα. 

#include <iostream>
#include <vector>

void enumerate(const std::vector<char>& A, int k) {
   int n = A.size();

   // Αναπαράσταση του αριθμού στο n-αδικό σύστημα.
   std::vector<int> pos(k, 0);
   while(true) {
      for (int i = 0; i < k; ++i) {
         ++pos[i];
         if (pos[i] < n) break;
         // Αν έχουμε κρατούμενο πρέπει να συνεχίσουμε στα επόμενα ψηφία.
         pos[i] = 0;
         // Έλεγχος αν είμαστε στο n^k - 1.
         if (i == k - 1) return;
      }
      // Τύπωση διάταξης.
      for (int i = k - 1; i >= 0; --i) {
         std::cout << A[pos[i]];
      }
      std::cout << std::endl;
   }
}

int main() {
   std::vector<char> A = {'a', 'b', 'c', 'd'};
   enumerate(A, 2);
   return 0;
}

/*
Αποτέλεσμα:
ab
ac
ad
ba
bb
bc
bd
ca
cb
cc
cd
da
db
dc
dd
*/

 Δείτε επίσης 
 Διάταξη
 Βασική αρχή απαρίθμησης
 Συνδυασμός

 Παραπομπές 

Κατηγορία:Συνδυαστική