[algogeeks] Re: Buying candy

2016-03-26 Thread Igor Pro 
It is like bubble sort type of algorithm. I'm not tested it on different 
data sets, created just for fun and your critic)

struct valuePos {int val; int pos;}
valuePos[,] data = new valuePos[n,n]; // assign input data array to [val] 
properties
// initialize by maximum val in data +1 or just unreachable value
// if index is not in use, calculated CompetitiveSwaps value will be less 
than zero and we use this as flag
int[] CompetitiveSwaps = {1,1,...}; // array of values to compare
int[] indexCount = {0,0,0...,0}; // size of n

sort each column of data by val

// input matrixval(index) after sort
6(1) 200(1)   20(1)150(1)   | 4(2)  3(2) 2(2)10(3)
4(2) 3(2)  2(2)  100(2)   | 6(1)  30(3)20(1)   
100(2)
300(3)  30(3)400(3)  10(3) | 300(3)  200(1)   300(4)  150(1)
400(4)  300(4)  300(4)  400(4)   | 400(4)   300(4)  400(3)  400(4)

int swapRow=1;

while(indexCount.indexof(0) != -1) // until all indexes will be used once, 
so all elements in indexCount array are "1"
{
 for(int i =0; i

[algogeeks] Re: Buying candy

2016-02-28 Thread Trevor 
Don  writes:

> 
> JVC is a multi-part algorithm which consists of a shortest augmenting
> path algorithm (JV) followed by a modified auction algorithm (C). It
> is best implemented as a sparse matrix. JVC is definitely an example
> of efficiency requiring a significant increase in complexity. The code
> implementing JVC is several times larger than Munkres or a standard
> auction algorithm.
> 
> Here are some references:
> 
> A description of JVC is here:
> O.E. Drummond, D.A. Castanon, M.S. Bellovin.
> Comparison of 2-D Assignment for Sparse, Rect-
> angular, Floating Point, Cost Matrix. Journal of
> the SDI Panels on Tracking, Institute for Defense
> Analyses, Issue No.4, 1990, pp.4-81 to 4-97.
> 

Does anybody know where I can find/purchase this reference? I can't find it
on SPIE and googling didn't turn up anything either. It is
referenced a lot, so I am wondering where everyone is finding it.

Thanks!
Trevor



-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.

[algogeeks] Re: Buying candy

2012-03-05 Thread Don 
JVC is a multi-part algorithm which consists of a shortest augmenting
path algorithm (JV) followed by a modified auction algorithm (C). It
is best implemented as a sparse matrix. JVC is definitely an example
of efficiency requiring a significant increase in complexity. The code
implementing JVC is several times larger than Munkres or a standard
auction algorithm.

Here are some references:

The JV part is here

R. Jonker, A. Volgenant. A shortest augmenting
path algorithm for dense and sparse linear assign-
ment problems.Computing, Vol. 38, 1987, pp.325-
340.

A thorough evaluation of JVC is here:

D.B. Malkoff. Evaluation of the Jonker-Volgenant-
Castanon (JVC) Assignment Algorithm for Track
Association Proceedings of the SPIE Aerosense'97
Conf. on Signal Proc., Sensor Fusion, and Target
Recognition, Vol. 3068, 1997, pp. 228-239.

A description of JVC is here:
O.E. Drummond, D.A. Castanon, M.S. Bellovin.
Comparison of 2-D Assignment for Sparse, Rect-
angular, Floating Point, Cost Matrix. Journal of
the SDI Panels on Tracking, Institute for Defense
Analyses, Issue No.4, 1990, pp.4-81 to 4-97.



On Mar 3, 10:15 pm, Dave dave_and_da...@juno.com wrote:
 @Don: I've looked for a description of Jonker-Volgenant-Castanon, but
 haven't found one. Can you provide a reference?

 Dave



 On Tuesday, February 28, 2012 11:53:22 AM UTC-6, Don wrote:
  Dave's answer, the Hungarian Algorithm, is correct because it does
  meet the requirements of the problem.
  There is another algorithm called Jonker-Volgenant-Castanon (JVC)
  which can be proven to be faster both on average and in worst case,
  than the Hungarian Algorithm. Both solutions are sure to find the best
  solution, which is not true of any ad hoc or greedy algorithm. For
  years, the Munkres algorithm was the best known solution, but JVC is
  significantly faster than Munkres.

  Don

  On Feb 28, 11:39 am, Don dondod...@gmail.com wrote:
   Yes, the tags constrain him to buy exactly one candy from each row and
   each column.
   There is a slightly better algorithm than Hungarian.
   Don

   On Feb 28, 11:33 am, Dave dave_and_da...@juno.com wrote:

@Don: Based on your example, there seems to be an unstated requirement
that Bob can and must buy exactly one candy from each row and each
column.

This is an assignment problem (see en.wikipedia.org/wiki/
Assignment_problem), and can be solved in O(N^3) by the Hungarian
Algorithm (see en.wikipedia.org/wiki/Hungarian_algorithm).

Dave

On Feb 28, 9:27 am, Don dondod...@gmail.com wrote:

 Little Bob likes candy, and he wants to buy all the candy he can get
 for the smallest price. At the store there is a big table with candy
 arranged in an NxN grid. Each candy has a price, Pij where i is the
 row and j is the column in which the candy is located. The store
  owner
 gives Bob N tags numbered 1..N. Bob can place one tag at the top of
 each column indicating the piece of candy he will buy from that
 column.

 Bob is smart enough to realize that he should not always buy the
  least
 expensive candy. For example, consider this price grid:

  1   20
  5   50

 In this case, buying the candy priced 1 would force him to buy the
 candy priced 50, for a total cost of 51. He is better off buying the
 second candy in the first column, allowing him to buy the first
  candy
 in the second column for a total price of 25.

 For a 2x2 case, considering all the possibilities is easy enough.
 There are only two choices. But as N increases, the number of ways
  to
 select N candies increases as N!, and Bob doesn't have time for an
 algorithm which requires more than polynomial time to execute.

 What algorithm should Bob use to buy N pieces of candy for the
 smallest cost?- Hide quoted text -

- Show quoted text -- Hide quoted text -

   - Show quoted text -- Hide quoted text -

 - Show quoted text -

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: Buying candy

2012-03-03 Thread Dave 
@Don: I've looked for a description of Jonker-Volgenant-Castanon, but 
haven't found one. Can you provide a reference?
 
Dave

On Tuesday, February 28, 2012 11:53:22 AM UTC-6, Don wrote:

 Dave's answer, the Hungarian Algorithm, is correct because it does 
 meet the requirements of the problem. 
 There is another algorithm called Jonker-Volgenant-Castanon (JVC) 
 which can be proven to be faster both on average and in worst case, 
 than the Hungarian Algorithm. Both solutions are sure to find the best 
 solution, which is not true of any ad hoc or greedy algorithm. For 
 years, the Munkres algorithm was the best known solution, but JVC is 
 significantly faster than Munkres. 

 Don 

 On Feb 28, 11:39 am, Don dondod...@gmail.com wrote: 
  Yes, the tags constrain him to buy exactly one candy from each row and 
  each column. 
  There is a slightly better algorithm than Hungarian. 
  Don 
  
  On Feb 28, 11:33 am, Dave dave_and_da...@juno.com wrote: 
  
  
  
   @Don: Based on your example, there seems to be an unstated requirement 
   that Bob can and must buy exactly one candy from each row and each 
   column. 
  
   This is an assignment problem (see en.wikipedia.org/wiki/ 
   Assignment_problem), and can be solved in O(N^3) by the Hungarian 
   Algorithm (see en.wikipedia.org/wiki/Hungarian_algorithm). 
  
   Dave 
  
   On Feb 28, 9:27 am, Don dondod...@gmail.com wrote: 
  
Little Bob likes candy, and he wants to buy all the candy he can get 
for the smallest price. At the store there is a big table with candy 
arranged in an NxN grid. Each candy has a price, Pij where i is the 
row and j is the column in which the candy is located. The store 
 owner 
gives Bob N tags numbered 1..N. Bob can place one tag at the top of 
each column indicating the piece of candy he will buy from that 
column. 
  
Bob is smart enough to realize that he should not always buy the 
 least 
expensive candy. For example, consider this price grid: 
  
 1   20 
 5   50 
  
In this case, buying the candy priced 1 would force him to buy the 
candy priced 50, for a total cost of 51. He is better off buying the 
second candy in the first column, allowing him to buy the first 
 candy 
in the second column for a total price of 25. 
  
For a 2x2 case, considering all the possibilities is easy enough. 
There are only two choices. But as N increases, the number of ways 
 to 
select N candies increases as N!, and Bob doesn't have time for an 
algorithm which requires more than polynomial time to execute. 
  
What algorithm should Bob use to buy N pieces of candy for the 
smallest cost?- Hide quoted text - 
  
   - Show quoted text -- Hide quoted text - 
  
  - Show quoted text -

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To view this discussion on the web visit 
https://groups.google.com/d/msg/algogeeks/-/v8w2R9Lq69MJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: Buying candy

2012-02-28 Thread Dave 
@Don: Based on your example, there seems to be an unstated requirement
that Bob can and must buy exactly one candy from each row and each
column.

This is an assignment problem (see en.wikipedia.org/wiki/
Assignment_problem), and can be solved in O(N^3) by the Hungarian
Algorithm (see en.wikipedia.org/wiki/Hungarian_algorithm).

Dave

On Feb 28, 9:27 am, Don dondod...@gmail.com wrote:
 Little Bob likes candy, and he wants to buy all the candy he can get
 for the smallest price. At the store there is a big table with candy
 arranged in an NxN grid. Each candy has a price, Pij where i is the
 row and j is the column in which the candy is located. The store owner
 gives Bob N tags numbered 1..N. Bob can place one tag at the top of
 each column indicating the piece of candy he will buy from that
 column.

 Bob is smart enough to realize that he should not always buy the least
 expensive candy. For example, consider this price grid:

  1   20
  5   50

 In this case, buying the candy priced 1 would force him to buy the
 candy priced 50, for a total cost of 51. He is better off buying the
 second candy in the first column, allowing him to buy the first candy
 in the second column for a total price of 25.

 For a 2x2 case, considering all the possibilities is easy enough.
 There are only two choices. But as N increases, the number of ways to
 select N candies increases as N!, and Bob doesn't have time for an
 algorithm which requires more than polynomial time to execute.

 What algorithm should Bob use to buy N pieces of candy for the
 smallest cost?

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: Buying candy

2012-02-28 Thread Don 
Yes, the tags constrain him to buy exactly one candy from each row and
each column.
There is a slightly better algorithm than Hungarian.
Don

On Feb 28, 11:33 am, Dave dave_and_da...@juno.com wrote:
 @Don: Based on your example, there seems to be an unstated requirement
 that Bob can and must buy exactly one candy from each row and each
 column.

 This is an assignment problem (see en.wikipedia.org/wiki/
 Assignment_problem), and can be solved in O(N^3) by the Hungarian
 Algorithm (see en.wikipedia.org/wiki/Hungarian_algorithm).

 Dave

 On Feb 28, 9:27 am, Don dondod...@gmail.com wrote:



  Little Bob likes candy, and he wants to buy all the candy he can get
  for the smallest price. At the store there is a big table with candy
  arranged in an NxN grid. Each candy has a price, Pij where i is the
  row and j is the column in which the candy is located. The store owner
  gives Bob N tags numbered 1..N. Bob can place one tag at the top of
  each column indicating the piece of candy he will buy from that
  column.

  Bob is smart enough to realize that he should not always buy the least
  expensive candy. For example, consider this price grid:

   1   20
   5   50

  In this case, buying the candy priced 1 would force him to buy the
  candy priced 50, for a total cost of 51. He is better off buying the
  second candy in the first column, allowing him to buy the first candy
  in the second column for a total price of 25.

  For a 2x2 case, considering all the possibilities is easy enough.
  There are only two choices. But as N increases, the number of ways to
  select N candies increases as N!, and Bob doesn't have time for an
  algorithm which requires more than polynomial time to execute.

  What algorithm should Bob use to buy N pieces of candy for the
  smallest cost?- Hide quoted text -

 - Show quoted text -

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: Buying candy

2012-02-28 Thread Don 
Dave's answer, the Hungarian Algorithm, is correct because it does
meet the requirements of the problem.
There is another algorithm called Jonker-Volgenant-Castanon (JVC)
which can be proven to be faster both on average and in worst case,
than the Hungarian Algorithm. Both solutions are sure to find the best
solution, which is not true of any ad hoc or greedy algorithm. For
years, the Munkres algorithm was the best known solution, but JVC is
significantly faster than Munkres.

Don

On Feb 28, 11:39 am, Don dondod...@gmail.com wrote:
 Yes, the tags constrain him to buy exactly one candy from each row and
 each column.
 There is a slightly better algorithm than Hungarian.
 Don

 On Feb 28, 11:33 am, Dave dave_and_da...@juno.com wrote:



  @Don: Based on your example, there seems to be an unstated requirement
  that Bob can and must buy exactly one candy from each row and each
  column.

  This is an assignment problem (see en.wikipedia.org/wiki/
  Assignment_problem), and can be solved in O(N^3) by the Hungarian
  Algorithm (see en.wikipedia.org/wiki/Hungarian_algorithm).

  Dave

  On Feb 28, 9:27 am, Don dondod...@gmail.com wrote:

   Little Bob likes candy, and he wants to buy all the candy he can get
   for the smallest price. At the store there is a big table with candy
   arranged in an NxN grid. Each candy has a price, Pij where i is the
   row and j is the column in which the candy is located. The store owner
   gives Bob N tags numbered 1..N. Bob can place one tag at the top of
   each column indicating the piece of candy he will buy from that
   column.

   Bob is smart enough to realize that he should not always buy the least
   expensive candy. For example, consider this price grid:

    1   20
    5   50

   In this case, buying the candy priced 1 would force him to buy the
   candy priced 50, for a total cost of 51. He is better off buying the
   second candy in the first column, allowing him to buy the first candy
   in the second column for a total price of 25.

   For a 2x2 case, considering all the possibilities is easy enough.
   There are only two choices. But as N increases, the number of ways to
   select N candies increases as N!, and Bob doesn't have time for an
   algorithm which requires more than polynomial time to execute.

   What algorithm should Bob use to buy N pieces of candy for the
   smallest cost?- Hide quoted text -

  - Show quoted text -- Hide quoted text -

 - Show quoted text -

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.