Wednesday, March 16, 2011

Permutations of M elements out of N elements checking for repetition

This function finds permutations of M elements out of N elements, checking not to output the same permutation twice in case that there are repetitions.

-----------------------------------------

public static ArrayList<ArrayList<String>> P_m_of_n_with_copies_present(ArrayList<String> items, int m, ArrayList<String> prev)
{
ArrayList<ArrayList<String>> permutations = new ArrayList<ArrayList<String>>();


if(prev.size() == m)
{
ArrayList<String> copy = new ArrayList<String>();
for(int i = 0; i < prev.size(); i++)
{
copy.add(prev.get(i));
}
permutations.add(copy);
}


for (int i = 0; i < items.size(); i++)
{
String first = items.get(0);
String ith = items.get(i);

if(first.equals(ith) && (i > 0))
{
continue;
}

items.set(i, first);
items.remove(0);

ArrayList<String> copy = new ArrayList<String>();
for(int j = 0; j < items.size(); j++)
{
copy.add(items.get(j));
}

prev.add(ith);
ArrayList<ArrayList<String>> thisPermutations = P_m_of_n_with_copies_present(copy, m, prev);
prev.remove(prev.size() - 1);
permutations.addAll(thisPermutations);
items.add(0, ith);
}


return permutations;
}

-----------------------------------------

No comments:

Post a Comment