// In this exercise you receive n and k and write a code that
// iterates over {0,...,n-1}^k, i.e., all k-uples (t_1,..., t_k)
// where t_1, ..., t_k are in {0,...,n-1}.
//
// The idea here is: for n = 2, we just iterate from 0 to 1<<k - 1.
// We would like to do the same for operations in base n. The only
// think we need is to implement the operatiosn "ADD 1" in base n.
//
// For example, with n = 3 and k = 4 we need to print:
//
// 0 0 0 0  \
// 1 0 0 0  |
// 2 0 0 0  |
// 0 1 0 0  |
// 1 1 0 0  |
// 2 1 0 0  |
// 0 2 0 0  | n^k tuples
// 1 2 0 0  |
// 2 2 0 0  |
// 0 0 1 0  |
// ...      |
// 2 2 2 2  /
//
//


#include "stdio.h"

int t[100]; // say k <= 100


// This function prints all the tuples.
void iterate_and_print (int n, int k) {
   int i;
   // initialize t = (0,...,0)
   for (i = 0; i < k; ++i) t[i] = 0;
   do {
      for (i = 0; i < k; ++i) printf("%d ", t[i]);
      printf("\n");
   } while (next_tuple(n,k));
}


// This function finds the next tuple. It does like in the example,
// it increments one variable, if it < n, I return. If it is n, I
// increment the other variable recursively. It returns false if there
// is no next permutation.
int next_tuple(int n, int k) {
   int i;
   for (i = 0; i < k; ++i) {
      t[i]++;
      if (t[i] < n) return 1;
      else t[i] = 0;
   }
   return 0;
}


int main() {
   iterate_and_print(3,4);
}