java - Algorithm to find the simplest combination of integers that has not yet been used -
i looking algorithm finding simplest combination of integers 0 5 (that 1 consists of fewest number of integers) has not yet been used (the used combinations in list).
the order matter , combinations should returned in list.
for example, list used numbers this:
{{0},{1},{2},{3},{4},{0,0},{0,1},{0,2},...,{2,1},{2,2},...,{1,5,4},...}
in case, algorithm should return list {5}, {5} combination consists of fewest integers.
if list looks this:
{{0},{1},{2},{3},{4},{5},{0,0},{0,1},{0,2},{0,3},{0,5},...}
the algorithm should return list 0 , 4 ({0,4}).
as used in java, java answer preferable pseudo-code or other programming languages usable too.
thank in advance!
i guess example 2 wrong: {{0},{1},{2},{3},{4},{5},{0,1},{0,2},{0,3},{0,5},...} smallest solution {0,0}, not {0,4}
complete solutions here:
import java.util.*; public class algorithm { static list<list<integer>> getchildren(list<integer> node){ list<list<integer>> children = new arraylist<list<integer>>(); for(int = 0; < 6; i++){ list<integer> child = new arraylist<integer>(node); child.add(i); children.add(child); } return children; } static list<integer> find(queue<list<integer>> queue, set<list<integer>> set){ for(;;){ list<integer> head = queue.poll(); if(!set.contains(head)){ return head; } else { for(list<integer> child : getchildren(head)){ queue.add(child); } } } } public static void main(string[] arg) { queue<list<integer>> queue = new linkedlist<list<integer>>(); for(int = 0; < 6; i++){ queue.add(collections.singletonlist(i)); } // example {{0},{1},{2},{3},{4},{5},{0,1},{0,2},{0,3},{0,5},...} set<list<integer>> task = new hashset<list<integer>>(); task.add(arrays.aslist(0)); task.add(arrays.aslist(1)); task.add(arrays.aslist(2)); task.add(arrays.aslist(3)); task.add(arrays.aslist(4)); task.add(arrays.aslist(5)); task.add(arrays.aslist(0, 1)); task.add(arrays.aslist(0, 2)); task.add(arrays.aslist(0, 3)); task.add(arrays.aslist(0, 5)); system.out.println(find(queue, task)); } }
Comments
Post a Comment