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

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

Για παράδειγμα, για το σύνολο A = \{ {\color{red}\alpha}, {\color{green}\beta}, {\color{blue}\gamma}, {\color{orange}\delta}\}, οι δυνατές διατάξεις με επανάληψη ανά 2 είναι οι εξής:
:({\color{red}\alpha}, {\color{red}\alpha}), ({\color{red}\alpha}, {\color{green}\beta}), ({\color{red}\alpha}, {\color{blue}\gamma}), ({\color{red}\alpha}, {\color{orange}\delta}), 
:({\color{green}\beta}, {\color{red}\alpha}), ({\color{green}\beta}, {\color{green}\beta}), ({\color{green}\beta}, {\color{blue}\gamma}), ({\color{green}\beta}, {\color{orange}\delta}),
:({\color{blue}\gamma}, {\color{red}\alpha}), ({\color{blue}\gamma}, {\color{green}\beta}), ({\color{blue}\gamma}, {\color{blue}\gamma}), ({\color{blue}\gamma}, {\color{orange}\delta}),
:({\color{orange}\delta}, {\color{red}\alpha}), ({\color{orange}\delta}, {\color{green}\beta}), ({\color{orange}\delta}, {\color{blue}\gamma}), ({\color{orange}\delta}, {\color{orange}\delta}),
Μερικές από τις δυνατές διατάξεις με επανάληψη μεγέθους 3 είναι οι εξής: ({\color{red}\alpha}, {\color{orange}\delta}, {\color{red}\alpha}), ({\color{blue}\gamma}, {\color{green}\beta}, {\color{red}\alpha}) και ({\color{red}\alpha}, {\color{green}\beta}, {\color{blue}\gamma}).

Στις διατάξεις, τα στοιχεία της k-άδας πρέπει να είναι όλα διαφορετικά μεταξύ τους, δηλαδή οι τριάδες ({\color{red}\alpha}, {\color{green}\beta}, {\color{red}\alpha}) και ({\color{orange}\delta}, {\color{orange}\delta}, {\color{red}\alpha}) δεν είναι διατάξεις. Στους  συνδυασμούς n ανά k, τα στοιχεία πρέπει πάλι να είναι διαφορετικά και η σειρά των στοιχείων της k-άδας δεν έχει σημασία, δηλαδή ({\color{red}\alpha}, {\color{green}\beta}, {\color{blue}\gamma}) και ({\color{blue}\gamma}, {\color{green}\beta}, {\color{red}\alpha}) είναι ο ίδιος συνδυασμός.

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

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

 = n^k.
}}
## Παραδείγματα

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

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

*Απάντηση* 

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

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

*Απάντηση*

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

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

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

Στο αρχικό παράδειγμα, θα διατρέξουμε τους αριθμούς από το 0 έως το 4^2 -1 = 15 στο σύστημα αρίθμησης με βάση το 4 και θα χρησιμοποιήσουμε την εξής αντιστοίχηση:
:0 \to \alpha, 1 \to \beta, 2 \to \gamma, 3 \to \delta.
Επομένως, ο αριθμός 6 είναι το 12_4 στο τετραδικό σύστημα αρίθμησης (καθώς 1 \cdot 4 + 2 \cdot 4^0 = 6) και αντιστοιχεί στην διάταξη με επανάληψη ({\color{green}\beta}, {\color{blue}\gamma}).

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


```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
*/
```


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

## Παραπομπές


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