// BaseNCounting.java
// Counts in k-digit baseN from 00..00 to dd..dd where (d == n-1).

import java.util.*;

public class BaseNCounting {

  public static void main(String[] args) {
    test1();
    test2();
  }

  public static void test1() {
    BaseNCounter bnc = new BaseNCounter(4,2);
    while (bnc.hasNext()) {
      int[] a = bnc.next();
      System.out.println(Arrays.toString(a));
    }
  }
  
  public static void test2() {
    Scanner scanner = new Scanner(System.in);
    System.out.print("Enter n (base): ");
    int n = scanner.nextInt();
    System.out.print("Enter k (# of digits): ");
    int k = scanner.nextInt();

    BaseNCounter bnc = new BaseNCounter(n,k);
    System.out.println("Counting in base " + n + " with " + k + " digits:");
    int counter = 0;
    while (bnc.hasNext()) {
      int[] next = bnc.next();
      System.out.println(Arrays.toString(next));
      counter++;
    }
    System.out.println("total = " + counter);
    System.out.println("Note that this equals " + n + "^" + k + " = " + (int)Math.pow(n,k));
  }
}

//////////////////////////////////////
// BaseNCounter
//
// You do not need to write the code below here.
// You just need to be able to USE it.
//////////////////////////////////////

class BaseNCounter {
  private int n, k;
  private int index = 0;
  private boolean hasNext = true;
    
  // n = base, k = # of diigts
  public BaseNCounter(int n, int k) {
    this.n = n;
    this.k = k;
  }

  public boolean hasNext() { return hasNext; }

  public int[] next() {
    if (!hasNext) return null;
    // the 1 bits of "index" indicate which numbers to include in this subset
    int[] result = new int[k];
    int digits = index++;
    hasNext = false;
    for (int i=k-1; i>=0; i--) {
      int digit = digits%n;
      result[i] = digit;
      digits /= n;
      if (digit < n-1) hasNext = true;
    }
    return result;
  }
}