Piet Souris

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.
Arrays.sort(transpose(a), comparator);
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.

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?    

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?

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.

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.

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

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

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
map.put("forward", p -> new Pair(p.x + 1, p.y) ;   // et cetera, assuming Pair is immutable, or else use Salvins Consumer.
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.

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!

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.

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.

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:
       var list = List.of(            1L,            (long) Math.pow(2, 20),            (long) Math.pow(2, 21),            (long) Math.pow(2, 22), // et cetera, 14 keys in the map and I have a Map creator like:
   private static Map<Integer, List<Long>> createMap(long from, long to) {        var map = LongStream.range(from, to)            .boxed()            .collect(groupingBy(Long::bitCount));        return map;    } and I have a method to get the bits set in a long:
   private static int[] bits(long[] i) {        return BitSet.valueOf(i).stream().toArray();    }
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:
       for (int i = 0; i < list.size() - 1; i++) {            System.out.println(i);            var map = createMap(list.get(i), list.get(i + 1));            map.values().stream()                .flatMap(List::stream)   // turns a List into a series of its elements                .forEach(l -> {                    Arrays.stream(bits(new long[] {l})). // et cetera
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.

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...

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.

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.