1

okay so we basically have this question to answer, but I am very confused and don't know how to use recursion to get all possible combinations.. Please someone save me!

Write a public static method threadings, which takes an int n (representing the number of beads on each necklace) and a Set of Strings (representing the available bead colours; your code must not alter this Set),and returns a Set of ArrayLists of Strings, representing all the orders in which n beads of the given colours can be threaded. If n < 1, return a Set containing just one, empty, ArrayList.

Examples of correct behaviour:

• threadings(0, {red,green}) = {[]}

• threadings(1, {red,green}) = {[red],[green]}

• threadings(2, {red,green}) = {[red,red],[red,green],[green,red],[green,green]}

• threadings(3, {red}) = {[red,red,red]}

Hint: you will probably want threadings to call itself recursively, although full marks are available for any correct method.

This is what I have written until now:

 public static HashSet<ArrayList<String>> threadings (int n, Set<String> colours){
    HashSet<ArrayList<String>> result= new HashSet<ArrayList<String>>();
    ArrayList<String> inresult= new ArrayList<String>();
    String[] col= new String[colours.size()];
    if (n==0){
        result.add(inresult);
        return result;
    }else{

    }
}
Jaymin Panchal
  • 2,797
  • 2
  • 27
  • 31
Patricia Milou
  • 11
  • 2
  • [Found this quickly on Google.](http://www.geeksforgeeks.org/print-all-possible-combinations-of-r-elements-in-a-given-array-of-size-n/) – Salem Apr 02 '17 at 16:21
  • Or on stackoverflow: http://stackoverflow.com/a/42911720/5057029 – DontPanic Apr 02 '17 at 16:35
  • Refer to [this](http://stackoverflow.com/questions/7218923/possible-combinations-of-a-list) question. Working with sets will be similar – Ivan Pronin Apr 02 '17 at 16:36
  • 1
    Is recursion the problem? Ever since I was a beginner in recursion, I have thought of it this way: When coding `threadings(n, colours)`, imagine you already have a method that will give you the possible threadings for `n - 1` beads and the same colours. You haven’t yet, just imagine you have, and you will have soon, I promise. Then coding the method is not so hard. – Ole V.V. Apr 02 '17 at 17:16

1 Answers1

0

Try this:

public static HashSet<ArrayList<String>> threadings (int n, Set<String> colours) {
    List<String> colorsList = new ArrayList<>(colours);
    ArrayList<String> resultList = new ArrayList<>();
    HashSet<ArrayList<String>> result = new HashSet<ArrayList<String>>();
    int carry;
    int[] indices = new int[n];
    do
    {
        for(int index : indices) {
            resultList.add(colorsList.get(index));
        }
        result.add(resultList);
        resultList = new ArrayList<>();

        carry = 1;
        for(int i = indices.length - 1; i >= 0; i--)
        {
            if(carry == 0)
                break;

            indices[i] += carry;
            carry = 0;

            if(indices[i] == colorsList.size())
            {
                carry = 1;
                indices[i] = 0;
            }
        }
    }
    while(carry != 1);

    return result;
}
coolesh
  • 1
  • 1