• 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
  • Ron McLeod
  • Rob Spoor
  • Tim Cooke
  • Junilu Lacar
Sheriffs:
  • Henry Wong
  • Liutauras Vilda
  • Jeanne Boyarsky
Saloon Keepers:
  • Jesse Silverman
  • Tim Holloway
  • Stephan van Hulst
  • Tim Moores
  • Carey Brown
Bartenders:
  • Al Hobbs
  • Mikalai Zaikin
  • Piet Souris

A little challenge I got with arrays

 
Greenhorn
Posts: 3
1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
input from the user int 'n'. Given an array filled in with numbers: every number from '1' to 'n' appears twice in the array. (when n=2: two 1's two 2's) the goal is to sort the numbers in the array so that the distance from every pair of numbers will be the same as the value of the number.
Example:




as you can see, the distance from the first '3' to the next '3' is 3, the distance from the first '2' to the next '2' is 2 and so on.

The length of the array will be n*2.
There are some values of 'n' which would not be possible to sort (like 10,2)

What I have tried:

I have tried to fill the array with n=5, and search for a kind of a pattern.




couldn't find any pattern.
 
lowercase baba
Posts: 13003
66
Chrome Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
i'm not sure this is possible.  for the array {1,1,2,2}, the two '1's have to be next to each other, so there is no way for a number to be between the two '2's, so they can't be two spots apart.

Or am I misunderstanding the problem?
 
Bartender
Posts: 3323
86
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
The OP did mention there isn't a solution for all values of n, for example 2 and 10.
 
fred rosenberger
lowercase baba
Posts: 13003
66
Chrome Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
ah...glossed right over that when I read it. thanks
 
Sheriff
Posts: 7111
184
Eclipse IDE Postgres Database VI Editor Chrome Java Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I'm not sure there is a trivial solution to this.  I wrote a brute force program because I noticed that some sequences have more than one solution:

String: 11223344
11342324
11423243
23243114
34232411
41134232
42324311

String: 1122334455
1134532425
1152423543
2325341154
2423543115
3453242511
3523245114
4115423253
4511435232
5113453242
5242354311

It looks like "112233445566" has no solution.  (My program is still working on "11223344556677".)  Also, notice that half the solutions are just the reverse of other solutions.  
 
Marshal
Posts: 74054
332
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Welcome to the Ranch

This looks a better fit for one of our other fora, so I shall move you.
 
Yehuda Hh
Greenhorn
Posts: 3
1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:Welcome to the Ranch

This looks a better fit for one of our other fora, so I shall move you.


Sure! If you think is fits there more
 
Yehuda Hh
Greenhorn
Posts: 3
1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Knute Snortum wrote:I'm not sure there is a trivial solution to this.  I wrote a brute force program because I noticed that some sequences have more than one solution:

String: 11223344
11342324
11423243
23243114
34232411
41134232
42324311

String: 1122334455
1134532425
1152423543
2325341154
2423543115
3453242511
3523245114
4115423253
4511435232
5113453242
5242354311

It looks like "112233445566" has no solution.  (My program is still working on "11223344556677".)  Also, notice that half the solutions are just the reverse of other solutions.  


Yes. For n=6 there is no solutions.
I know there are solutions to: 1,4,5,8,12
 
Knute Snortum
Sheriff
Posts: 7111
184
Eclipse IDE Postgres Database VI Editor Chrome Java Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Well, brute force definitely does not work.  You will have to find some clever algorithm to find solutions.  I will probably keep thinking about this...

Where did you find this challenge?  I'm just curious.
 
Bartender
Posts: 4633
182
  • Likes 2
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Just had a try with this one. Indeed, brute force does have some O(N!) characterization, but for N <= 50 you can get some results, with some optimization.
It is, for instance, very easy to proof that if there is a solution for some N, then there is a solution in which the array starts with N. So, if you try starting with N at position 0 and that gives no solution, then there is no solution. Using this and some other trickes, I managed to get solutions for N = 1, 4, 5, 8, 9, 12, 13, 16, 17, 20, 21, 24, 25, 28, 29, 32, 33, 36, 44, 45.

For those N's that are not summed up: if N <= 17, then there is no solution, for the bigger N's there is probably no solution, but I am not sure.

Does anyone know a handy term for this problem, so that we can Google for some clever articles?

Here is a solution for N = 45:

[45, 43, 44, 40, 38, 42, 35, 41, 32, 30, 39, 27, 25, 37, 21, 36, 17, 15, 34, 6, 33, 9, 7, 31, 3, 6, 29, 3, 28, 7, 9, 26, 15, 17, 24, 21, 23, 25, 27, 30, 32, 35, 38, 40, 43, 45, 44, 42, 41, 39, 37, 36, 34, 33, 31, 29, 28, 26, 24, 23, 22, 20, 18, 16, 19, 13, 8, 2, 4, 2, 14, 5, 4, 12, 8, 11, 5, 10, 13, 16, 18, 20, 22, 19, 14, 12, 11, 10, 1, 1]
 
Knute Snortum
Sheriff
Posts: 7111
184
Eclipse IDE Postgres Database VI Editor Chrome Java Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

It is, for instance, very easy to proof that if there is a solution for some N, then there is a solution in which the array starts with N.


I guessed that this is so, but I didn't have a proof for it.  I wouldn't mind seeing your "very easy" proof!
 
Creator of Enthuware JWS+ V6
Posts: 3395
312
Android Eclipse IDE Chrome
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Congratulations, your question was selected for this month's Journal  

Have a Cow!
 
Greenhorn
Posts: 22
3
Netbeans IDE Chrome Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I'm pretty sure this is a problem you cannot solve with a deterministic algorithm.

Two non-deterministic techniques that I think would apply themselves and achieve solutions fairly quickly (if/when they exist) are "genetic algorithm" and "ant colony algorithm".

So tempted to work up something - but even spending the time writing this means I'm procrastinating with something else :-(

Jim
 
Piet Souris
Bartender
Posts: 4633
182
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Knute Snortum wrote:

It is, for instance, very easy to proof that if there is a solution for some N, then there is a solution in which the array starts with N.


I guessed that this is so, but I didn't have a proof for it.  I wouldn't mind seeing your "very easy" proof!


I must admit to having made a blunder. I only proved it for two simple cases, but I have been unable to prove it for a more general case. I apologize for my statement.

What is easy to prove is that a necessary condition for N to have a solution is that either N or N - 1 is dividable by 4. I have so far been unable to prove that this is also a sufficient condition.
So, for N = 2, 3, 6, 7, 10, 11, et cetera, there is no solution.

If you try N = 40, then there is no solution for N at location 0. If that means that there is no solution for N = 40, then the condition mentioned is not sufficient.

So far I've tried to use the simplex algorithm, as known from operational research, but without success, so far.

Applying a genetic algorithm sounds interesting, haven't given this a thought yet. Keep us informed!

For the interested reader: here are my proofs:

First: if there is a solution for N, then there is a solution that starts with N.
"Proof": if the solution ends with N, then simply reverse the array. And if it is true that for every J < N that is to the left of the first N or to the right of the second N, also the second J is at that same side, then rotate the array such that it is still a solution and it starts with N. That's why I called it "very easy".

What I forgot to prove, and haven't been able to do so, is the obvious situation like the array starting with: 2 N 2 ...
I am still working on a kind of bubble sort (swap N with the first 2, then swap the second 2 with its element to the right, et cetera, but this is a nightmare for the general case.

The necessity that either N or N-1 is dividable by 4:

Let j go to location x(j), then the second j goes to location x(j) + j. That is the case for j = 1, 2, ..., N.
Now, if we sum all these locations, we get:

x(1) + x(1) + 1 + x(2) + x(2) + 2 + ... + x(N) + x(N) + N.  (1)

This sum must be equal to the sum of all the locations: 0 + 1 + 2 + ... + 2N - 1.  (2)

Since (1) = (2) we get that

x(1) + ... + x(n) = N * (N-1) * 3 / 4

Since the left hand side is an integer, so must be the right hand side. Now, since either N or N-1 is odd, we must have that the other one is dividable by 4

 
Every plan is a little cooler if you have a blimp. And a tiny ad.
Thread Boost feature
https://coderanch.com/t/674455/Thread-Boost-feature
reply
    Bookmark Topic Watch Topic
  • New Topic