• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Clustering number pairs - Java

 
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I have a set of number pairs in random order in an array as follows:

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

I need to link all these numbers based on the common number when comparing pairs. So my expected output would be: 1,2,7,3,4,5,6.
Following is one of the algorithms found in this forum, but it is not clear to me.

1) Create an array of int, as long as the number of points.
2) Initialize each array element to its own index.
3) Sort the pairs by their lower-numbered member, secondarily by their higher member, in ascending order
4) For each pair, in sorted order
a) choose the lower point number
b) read the value at that array index
c) set the value at the higher array index to that value.
This is what I have understood. I use java for this.
Step 1-2
int[] data = new int[12];
int[0] = 5;
int[1] = 6;
int[2] = 2;
int[3] = 7;
int[4] = 3;
int[5] = 7;
int[6] = 1;
int[7] = 2;
int[8] = 3;
int[9] = 4;
int[10] = 4;
int[11] = 5;
--
--
Step3: This is what i am not clear, Does it mean sorting this way:
(i) Sort by lowest number in the pair: (1,2) (2,7) (3,7)(3,4) (4,5) (5,6)
(ii)Sort by Higher number in the pair: (1,2) (3,4) (4,5) (5,6) (2,7) (3,7) and putting the elements of
each into two arrays

step4: Do i have to iterate through the two arrays? I am not clear...
 
Marshal
Posts: 79177
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Start thinking object‑oriented. What sort of object can you design which would contain those two numbers?
 
Brian Rupasinghe
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:Start thinking object‑oriented. What sort of object can you design which would contain those two numbers?



I can sort them in that order, keeping each pair of numbers in lists of an arraylist.
What i am not clear is the steps 3 and 4 in the algorithm. Can you explain it bit clearly.
 
Campbell Ritchie
Marshal
Posts: 79177
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Start by thinking object‑oriented. Create an object which will contain your two numbers. Delete stages 1 to 4 inclusive from your list.
 
Brian Rupasinghe
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:Start by thinking object‑oriented. Create an object which will contain your two numbers. Delete stages 1 to 4 inclusive from your list.



Do you mean some thing like this?

public class Testobject {
private int x;
private int y;
public void SetNumber (int a, int b)
{
this.x = a;
this.y = b;
}
public List getNumberPair() {
List lst = new ArrayList();
lst.add(0, x);
lst.add(1, y);
return lst;
}

What is meant by delete stages 1-4??
 
Campbell Ritchie
Marshal
Posts: 79177
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I mean the stage 1 to 4 of your original suggestion are no use.
The class you have quoted is pretty poorly designed. Why did you not call it Pair? Why didn’t you mark both fields final? Why hasn’t it got a constructor? Why does that List appear mysteriously in the middle of the class?

It looks as if you have got a fixation about putting things in Lists and you have not explained why you need Lists. Before you can write any apps, you need to work out what they are going to do. Draw a diagram of how those pairs are supposed to relate to each other. That will give you some idea about their relationships. Post the diagram if possible.
 
Brian Rupasinghe
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:I mean the stage 1 to 4 of your original suggestion are no use.
The class you have quoted is pretty poorly designed. Why did you not call it Pair? Why didn’t you mark both fields final? Why hasn’t it got a constructor? Why does that List appear mysteriously in the middle of the class?

It looks as if you have got a fixation about putting things in Lists and you have not explained why you need Lists. Before you can write any apps, you need to work out what they are going to do. Draw a diagram of how those pairs are supposed to relate to each other. That will give you some idea about their relationships. Post the diagram if possible.



Thanks. I have modified the class. But i cannot understand why members are to be declared as final.
By the way, I thought of using List to swap value pairs easily. The design is about linking the common number of pairs.
If i can order these pairs such as (1,2) (2,7) (3,7) (3,4) (4,5) (5,6), the sequence can be obtained easily which is:
1,2,7,3,4,5,6


public class pair {
private int x;
private int y;
private List lst = new ArrayList();
public pair(int a, int b)
{
this.x = a;
this.y = b;
}
public void SetNumber (int a, int b)
{
this.x = a;
this.y = b;
}
public List getNumberPair() {

lst.add(0, x);
lst.add(1, y);
return lst;
}
 
Campbell Ritchie
Marshal
Posts: 79177
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I suggested making the numbers final because I thought they would not change inside a particular pair. I might have been mistaken on that last point, however.
When you say things about lists and swapping it suggests you have gone one stage beyond what you want to do and are trying to think how to do it. Until you can draw a diagram showing the relationships between different pairs (or somethign along those lines), and whether their right and left numbers should be the same, how can you work out how to do it.
Where exactly did you find the algorithm you had yesterday? Did you understand what it does?
 
Consider Paul's rocket mass heater.
reply
    Bookmark Topic Watch Topic
  • New Topic