ArrayQuestion.java

import java.util.Scanner;   // for user input
import java.util.Arrays;    // to sort array

public class ArrayQuestion {

    /**
    *   Program: ArrayQuestion
    *   Purpose: Yahoo! Answers
    *   Creator: Chris Clarke
    *   Created: 02.08.2012
    */


/*
You are given two postive integers n and k.?
Your task is to fill an array of size n such that

All elements of A are integers in the range 1,2,...,k.
A is sorted in the increasing order.
Each of the integers 1,2,...,k appears at least once in the array.

Write a recursive function to do the following:

Report all possible ways of generating the array A.
Return the count of possibilities.
*/

    static int k, n;
    static int[] theArray;
    static int poss=0;

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);

        System.out.print("Enter array size: ");
        n = scan.nextInt();

        theArray = new int[n];

        System.out.print("Array range = 1, 2, ..., k.  Enter value for k: ");
        do {
            k = scan.nextInt();
            if (k>n) {
                System.out.println("k must not be more than array size (" + n + ")");
                System.out.print("Please re-enter k: ");
            }
        } while (k>n);

        int numDoubles = n-k;   // array size - range

        int[] addedArray = new int[numDoubles];

        for (int i=0; i<numDoubles; i++)
            addedArray[i] = 1;

        int pos = numDoubles-1;

        poss = getArray(pos, addedArray, true);

        System.out.println("Number of possibilities = " + poss);
    }

    public static void initialiseArray() {
        int j=1;
        for (int i=0; i<n; i++) {
            if (j<=k) {
                theArray[i] = j++;
            } else {
                theArray[i] = 0;
            }
        }
    }

    public static int getArray(int pos, int[] anArray, boolean display) {
        // recursive function
        int len = anArray.length;

        if (display) {
            initialiseArray();
            for (int i=0; i<len; i++) {
                theArray[i+k] = anArray[i];
            }

            Arrays.sort(theArray);

            for (int i=0; i<theArray.length; i++) {
                System.out.print(theArray[i]+" ");
            }
            System.out.println();
            poss++;
        }

        if (k==n) return 1;

        if (anArray[pos] < k) {
            anArray[pos]++;
            int temp = anArray[pos];
            while (pos<len-1) {
                anArray[++pos]=temp;
            }
            getArray(pos, anArray, true);
        } else if (pos>0) {
            getArray(--pos, anArray, false);
        }

        return poss;
    }
}