Java program having an infinite loop for no (?) reason

Question

I have two ArrayList<ArrayList<String>>'s thant are the same size. The following code checks to see if the corresponding ArrayLists have any elements that are equal. If they do, they are both shuffled and the program rechecks and repeats.

boolean b=true;
int counter=0;
while(b==true)
{
   for(int i=0; i<arraylist1.size(); i++)
   {
       for(int j=0; j<arraylist2.size(); j++)
       {
           for(String s1: arraylist1.get(i))
           {
               for(String s2: arraylist2.get(j))
               {
                  if(s1.equals(s2))
                  {
                     counter++;
                  }
               }      
           }
       }
   }

   if(counter==0)
   {
       b=false;
   }
   else
   {
       long random = System.nanoTime();
       Collections.shuffle(arraylist1, new Random(random));

       long random2 = System.nanoTime();
       Collections.shuffle(arraylist2, new Random(random2));

       counter=0;
   }           
}

What I know the problem is NOT: I know it is NOT the case that the two ArrayLists must have corresponding ArrayLists with the same element (i.e., there IS a shuffling of the ArrayLists such that all corresponding ArrayLists will have different elements). I also know it's not computational time.

What I think the problem may be: I think there is something inherently "unrandom" with the shuffling method I call, but honestly, I have no idea why this is not working. In fact, when I do this program with the code b=false at the end (to take me out of the loop no matter what and see how arraylist1 and arraylist2 compare) the ArrayLists are most of the time (correspondingly) different! Yet the program ALWAYS runs into an infinite loop despite this!

What exactly do you expect to happen here? Shuffling the lists isn't going to change the fact that they share a common element. Of course it results in an infinite loop; you've done nothing to break the condition. — Chris Hayes
– Chris Hayes, Commented Dec 2, 2013 at 0:55
"Having an infinite loop for no reason" - as a general rule of thumb, when you're not sure whether the bug exists in your code, or in the Java Libraries, go with your code. Libraries are pretty damn good — torquestomp
– torquestomp, Commented Dec 2, 2013 at 1:02
Since you are doing a lot of comparing I would use type List<Set<String>>. This way you don't have to check element by element, only the intersections of sets. — bcorso
– bcorso, Commented Dec 2, 2013 at 1:02

torquestomp · Accepted Answer · 2013-12-02 00:59:00Z

1

It seems like you want to compare strings in equivalent positions, not ALL strings - as Chris Hayes said, shuffling will do nothing to prevent s1 and s2 from being equal, they'll just be in different positions. It sounds like you need to be doing something like this instead:

for (int i = 0; i < arraylist1.size(); i++) {
  List<String> list1 = arraylist1.get(i);
  List<String> list2 = arraylist2.get(i);

  // Check if the two lists have any elements in common
  for (String s1 : list1) {
    if (list2.contains(s1)) {
      counter++;
    }
  }
}

answered Dec 2, 2013 at 0:59

torquestomp

3,35421 silver badges26 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Raj Raina Over a year ago

I see... I could just drop my j's so I only check at the i positions. Darn I hate when I miss simple things like this. But thanks :)

bcorso Over a year ago

I've also added a very similar answer as you but using sets. If you consolidate my answer into yours, i'll take mine down and upvote you.

bcorso · Accepted Answer · 2013-12-02 01:31:45Z

0

for(int i=0; i<listOfSets1.size(); i++){
    Set<String> set1 = new HashSet<String>(listOfSets1.get(i));
    Set<String> set2 = listOfSets2.get(i);

    // retainAll gives destructive intersection of set1 and set2
    if( !set1.retainAll(set2).isEmpty() )
        break;
}
// do something more than shuffle

Instead of using List<List<String>> use List<Set<String>>. This will allow you to do comparisons of two sets in O(n) instead of O(n²).

The O(n²) vs O(n) of List and Set respectively stems from the fact that it takes O(n) time to tell if an element is in a List and only O(1) to tell if an element is in a Set.

edited Dec 2, 2013 at 1:31

answered Dec 2, 2013 at 1:12

bcorso

47.5k10 gold badges66 silver badges76 bronze badges

Collectives™ on Stack Overflow

Java program having an infinite loop for no (?) reason

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related