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