Win a copy of Grokking Bitcoin this week in the Cloud/Virtualization forum!

since Mar 08, 2009

Netherlands

Cows and Likes

Cows

Total received

119

In last 30 days

9

Total given

76

Likes

Total received

588

Received in last 30 days

15

Total given

61

Given in last 30 days

5

Forums and Threads

Scavenger Hunt

Rancher Scavenger Hunt

Ranch Hand Scavenger Hunt

Greenhorn Scavenger Hunt

Hmmm...

if it were me, then I would produce a very simple int[] Comparator (that compares on the first elements), and do a sort on the transpose of the matrix.

But this is the Beginners Forum, and I don't think this exercise is easy at all. I would not use terms like 'very easy'. Let's wait for Michael to hear what he thinks.

if it were me, then I would produce a very simple int[] Comparator (that compares on the first elements), and do a sort on the transpose of the matrix.

But this is the Beginners Forum, and I don't think this exercise is easy at all. I would not use terms like 'very easy'. Let's wait for Michael to hear what he thinks.

3 hours ago

Campbell wrote:How can you have two classes with the same name in the same package? More likely there is another class called JFrame, minus the setDefaultCloseOperation() method.

Unlikely. But wanna make a bet on it?

8 hours ago

Or, for something completely different: if your first row = "b a d c", and you sort it, then the original indices (0 1 2 3) will now be 1 0 3 2. What does that mean for the other rows?

9 hours ago

hi Luc,

first of all: 'x' is not a legal character in the base-16 system. Second, your string, as int, does not fit into an int. The maximum value that you can use is "7FFFFFFF". If you do want your string to parse, use Integer.parseUnsignedInt.

first of all: 'x' is not a legal character in the base-16 system. Second, your string, as int, does not fit into an int. The maximum value that you can use is "7FFFFFFF". If you do want your string to parse, use Integer.parseUnsignedInt.

10 hours ago

hi Elliot,

welcome to the Ranch and enjoy the stay!

You have not mentioned anything about a package. Are you using the default package? If so, is it possible that you somewhere have another class Calculator that does not extend JFrame?

I copied your code into my IDE, albeit that I put all the classes in the same file (removing the 'public' from the classes) and it ran without any problems.

welcome to the Ranch and enjoy the stay!

You have not mentioned anything about a package. Are you using the default package? If so, is it possible that you somewhere have another class Calculator that does not extend JFrame?

I copied your code into my IDE, albeit that I put all the classes in the same file (removing the 'public' from the classes) and it ran without any problems.

10 hours ago

As OP writes, if you have 5, 3, 3 then that only counts for one inversion.

1 day ago

But first thing is removing duplicates while maintaining the order, and, depending on knowledge and experience,, that may not be that easy.

1 day ago

hi Knute,

I wanted to provide a possibility, but it boiled down to what Salvin already had. I used a static map<String, UnaryOperator<Pair>>, which I filled with

and in your processing, use p.x and p.y as row and column.

I myself would use an enum for this, but as you write: first a lambda way.

I wanted to provide a possibility, but it boiled down to what Salvin already had. I used a static map<String, UnaryOperator<Pair>>, which I filled with

and in your processing, use p.x and p.y as row and column.

I myself would use an enum for this, but as you write: first a lambda way.

2 days ago

hi Petros,

you certainly kept us very nicely busy for a couple of days, with whatever was the problem (clear as mud to me now ). A splendid moment therefore to stop. So, thank you, and keep'm coming!

you certainly kept us very nicely busy for a couple of days, with whatever was the problem (clear as mud to me now ). A splendid moment therefore to stop. So, thank you, and keep'm coming!

2 days ago

But I suspect that 'hasMatchingEdges' will take yet another pint!

About this takes forever, as I remarked:

A rough estimate is that when the size is n, and the average number of neighbors is m, then the coverage has between n/m and, say, limit = 1.5*n/m elements. So, brute forcing would get you the sum of (n over k), for k ranging from 1 to this limit.

With 18 vertices and a minimal coverage of 9, gives m = 2, so the number of calcultations is about 150K-250K. Half a second run time means about 200.000 checks/second.

If we have n = 34, m = 5; then brute force takes around 4 to 6 minutes or so. m = 2 does take forever.

About this takes forever, as I remarked:

A rough estimate is that when the size is n, and the average number of neighbors is m, then the coverage has between n/m and, say, limit = 1.5*n/m elements. So, brute forcing would get you the sum of (n over k), for k ranging from 1 to this limit.

With 18 vertices and a minimal coverage of 9, gives m = 2, so the number of calcultations is about 150K-250K. Half a second run time means about 200.000 checks/second.

If we have n = 34, m = 5; then brute force takes around 4 to 6 minutes or so. m = 2 does take forever.

2 days ago

hi Petros,

gaiined an experience, lost an illusion, as we say in Holland...

well, Mike is right (clever guy he is), my idea is nice for small sizes, but very inefficient for larger values. You better get the powerset via a more classic way. And besides, brute force takes forever.

So I decided to give my initial idea a go, creating a slightly extended adjacencyMap, and using some simple elimination process. It looks very promising, for instance creating a graph of 100 vertices 0...99, with an average outdegree of 25 (i.e. every vertex has on average 25 neighbors), I got this result [55, 52, 79, 17, 60, 82, 46]. Can't prove that this is a minimal coverage, but as said it looks promising, and the run time was less than a second.

Not brute force, but if you are interested in my code nevertheless, let me know and I'll drop it on my GitHub account.

gaiined an experience, lost an illusion, as we say in Holland...

well, Mike is right (clever guy he is), my idea is nice for small sizes, but very inefficient for larger values. You better get the powerset via a more classic way. And besides, brute force takes forever.

So I decided to give my initial idea a go, creating a slightly extended adjacencyMap, and using some simple elimination process. It looks very promising, for instance creating a graph of 100 vertices 0...99, with an average outdegree of 25 (i.e. every vertex has on average 25 neighbors), I got this result [55, 52, 79, 17, 60, 82, 46]. Can't prove that this is a minimal coverage, but as said it looks promising, and the run time was less than a second.

Not brute force, but if you are interested in my code nevertheless, let me know and I'll drop it on my GitHub account.

5 days ago

hi Petros,

I apologize, I did not realize that this is the Beginners Forum, since your task is not what I would call a beginners assignment.

I just made a very simplified demo version, to see if it worked and how I could do justice to Mike's remarks. I'll give some code to illustrate what I mean, but a bit reluctantly, since this is an assignment. But I hope you get some ideas to implement in your own code.

For instance, to create the Map I was talking about, I have this:

and I have a Map creator like:

and I have a method to get the bits set in a long:

The process is then: starting with bitCount 1, traverse the List<Long>, determine the bits of each long, and add the corresponding sets as I described before, testing for the size of the result. Currently, I do an O(n) operation for each long, to get an idea of the speed, but that should be O(n*n).

Like:

Well, it took 2 minutes to calculate 5 of the 14 keys so far, so the real thing would take a complete holiday, I guess. I can think of some optimizations, but at the cost of making the whole thing even more complicated. It is certainly more complicated than I thought at first.

Anyway, I hope it is clear what I am talking about. But I would certainly start with a graph of only a few elements, to test whatever you have.

I apologize, I did not realize that this is the Beginners Forum, since your task is not what I would call a beginners assignment.

I just made a very simplified demo version, to see if it worked and how I could do justice to Mike's remarks. I'll give some code to illustrate what I mean, but a bit reluctantly, since this is an assignment. But I hope you get some ideas to implement in your own code.

For instance, to create the Map I was talking about, I have this:

and I have a Map creator like:

and I have a method to get the bits set in a long:

The process is then: starting with bitCount 1, traverse the List<Long>, determine the bits of each long, and add the corresponding sets as I described before, testing for the size of the result. Currently, I do an O(n) operation for each long, to get an idea of the speed, but that should be O(n*n).

Like:

Well, it took 2 minutes to calculate 5 of the 14 keys so far, so the real thing would take a complete holiday, I guess. I can think of some optimizations, but at the cost of making the whole thing even more complicated. It is certainly more complicated than I thought at first.

Anyway, I hope it is clear what I am talking about. But I would certainly start with a graph of only a few elements, to test whatever you have.

5 days ago

Well, I do use recursion, but not in the way you write. Here, I generate all subsets of length 1, check whether any fulfills the requirement, then, starting from these, all subsets of length 2, eliminate all length 1 subsets, et cetera. You could do it the other way, but I don't think that would be more efficient. I've never done any tests on efficiency though (I do not need this on a daily basis), but anyway, wondering what teacher would torture his/her students with these kinds of misery...

Over to Petros...

Over to Petros...

5 days ago

hi Mike,

why not? My idea is based on this: if you have a vertex 1 that has neighbors 2, 3, and 4, then I have a map.entry<1, {1,2, 3, 4}. Likewise, if vertex 5 has neighbors 8 and 9, we have a map.entry<5, {5, 8, 9}> (so in fact a slightly extended adjescent list). If I then have a long with the bits 1 and 5 set, I make a Set of the two groups {1, 2, 3, 4} and {5, 8, 9} and see if the size is 34. Going from bitcounts 2 to 34 would (in the very long run) find the nminimal set.

Edit: my reply was before I read your edit. You're right, I made a "small" error isn caculating 2^34! But then you don't need to do that in one go. The series you showed is one that I use myself to generate all subsets: first all subsets length 1, then, based on that, those of size 2 (I did not do it in my routine, but then you can eliminate the 1 subsets, et cetera). Well, all in all not easy at all, but doable.

why not? My idea is based on this: if you have a vertex 1 that has neighbors 2, 3, and 4, then I have a map.entry<1, {1,2, 3, 4}. Likewise, if vertex 5 has neighbors 8 and 9, we have a map.entry<5, {5, 8, 9}> (so in fact a slightly extended adjescent list). If I then have a long with the bits 1 and 5 set, I make a Set of the two groups {1, 2, 3, 4} and {5, 8, 9} and see if the size is 34. Going from bitcounts 2 to 34 would (in the very long run) find the nminimal set.

Edit: my reply was before I read your edit. You're right, I made a "small" error isn caculating 2^34! But then you don't need to do that in one go. The series you showed is one that I use myself to generate all subsets: first all subsets length 1, then, based on that, those of size 2 (I did not do it in my routine, but then you can eliminate the 1 subsets, et cetera). Well, all in all not easy at all, but doable.

5 days ago

I don't quite follow. The idea was to find a minimal set of vertices that would cover the entire graph. What order do you have in mind? My idea waas to start with all subsets of size 1, then 2, et cetera, for which I thought the map was an easy way to implement that.

5 days ago