Build a chain of links from a list

Question

I have a list of key / value pairs, and I need to find the chains in the list where the value matches the key.

eg. from below can be 12, 23, 34 or 62, 23, 34

Key Value 1 2 3 4 2 3 6 2 

More than one value may point to the same key, but I need to store different "chains" for each unique starting and ending point. The list can be in any order.

I use Java, but I am a little fixated on how to solve this problem.

Please, help!

Answer 1

Recursion!

 import java.util.HashMap; import java.util.Map; public class Chain { private static Map< String , String > map; public static void main( String args[] ) { map = new HashMap< String , String >(); map.put( "1" , "2" ); map.put( "3" , "4" ); map.put( "2" , "3" ); map.put( "6" , "2" ); for ( String key : map.keySet() ) { System.out.print( "(" + key + "," + map.get( key ) + ")" ); recurse( map.get( key ) ); System.out.println(); } } private static void recurse( String value ) { if ( map.containsKey( value ) ) { System.out.print( " (" + value + "," + map.get( value ) + ")" ); recurse( map.get( value ) ); } } } 

It produces the following result:

 (3,4) (2,3) (3,4) (1,2) (2,3) (3,4) (6,2) (2,3) (3,4) 

Answer 2

Create a Map<Integer, List<Integer>> , save all your pairs on this map, and then iterate the map.

Pseudo Code:

 // 1st step foreach(key, value){ if(!map.containsKey(key)){ map.put(key, new ArrayList()); } map.get(key).add(value); } // 2nd step foreach(entry /* of map */){ if(map.containsKey(entry.value)){ // print pairs } } 

Obviously this is a pseudo code that will not compile, but it should get started

Answer 3

Since this looks like homework, I will give you tips that will help you solve the problem yourself, and not give you a complete solution.

• For any key on the map, you can get the corresponding value by calling Map.get(key) .
• You can use any value as a key to get its corresponding value (if any).
• You can Map.getKeys() over all keys on a map using Map.getKeys() .

If you want to print the chains, that should be enough. If you want to store chains in some other data structure, please provide additional information.