aspose file tools*
The moose likes Java in General and the fly likes Permutations Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Spring in Action this week in the Spring forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "Permutations" Watch "Permutations" New topic
Author

Permutations

ashok mandala
Greenhorn

Joined: Nov 23, 2012
Posts: 9
hi frnds i need help for the below problem

consider a permutation of first 'N' natural numbers 'good' if it doesn't have 'x' and 'x+1' appearing consecutively,
where (1 <= x <= N).
for example, for N=3, all 'good' permutations are:
1. {1,3,2}
2. {2,1,3}
3. {3,2,1}
Write a java program that takes an input 'N' and displays the number of possible 'good' permutations. So, for input
of 3 for 'n' above, we would print '3' as the output.
Suresh Sajja
Ranch Hand

Joined: May 12, 2009
Posts: 34

ashok mandala wrote:hi frnds i need help for the below problem

consider a permutation of first 'N' natural numbers 'good' if it doesn't have 'x' and 'x+1' appearing consecutively,
where (1 <= x <= N).
for example, for N=3, all 'good' permutations are:
1. {1,3,2}
2. {2,1,3}
3. {3,2,1}
Write a java program that takes an input 'N' and displays the number of possible 'good' permutations. So, for input
of 3 for 'n' above, we would print '3' as the output.


why not {2,3,1} is good permutation?


~Suresh
ashok mandala
Greenhorn

Joined: Nov 23, 2012
Posts: 9
we are considering that the permutation will be good if it doesn't have consecutive numbers........
Suresh Sajja
Ranch Hand

Joined: May 12, 2009
Posts: 34

Oh! i misread you original post.

I would approach this problem in two steps,

1. To come up with a algorithm that generate all the permutations of N numbers
2. filter the list to hold only good permutations



Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39416
    
  28
Welcome to the Ranch

Read Suresh Sajja’s post carefully; it contains good advice. I would suggest you filter each permutation before adding it to your list, however.
Please don’t use {} around your numbers, because that denotes a set. Use [] for a sequence. So [1, 2, 3] is a “bad” sequence and [3, 2, 1] is a “good” sequence.
ashok mandala
Greenhorn

Joined: Nov 23, 2012
Posts: 9
i got the logic for first step...
but dont know how to filter.....
help me out..........
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11419
    
  16

ashok mandala wrote:i got the logic for first step...
but dont know how to filter.....
help me out..........

How do YOU, personally, decide if a sequence is valid or not? Let's say I gave you this:

[2,5,3,4,1]

Is that 'good', or 'bad'? How do you know? can you write down the steps that an 8-year old child could follow to determine this?

The most important part of writing code does not involve your computer, but your brain + pencil + paper.


There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
mohammed irfan
Greenhorn

Joined: Feb 11, 2013
Posts: 2
according to this question a good permutation is,that doesn't have consecutive increasing numbers side by side...
for input 3 we can only have {[1,3,2],[3,1,2],[2,1,3],[3,2,1]} but we cant have {[1,2,3],[2,3,1],[]} i.e we can't have x,x+1 type arrangements....
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39416
    
  28
Welcome to the Ranch , Mohammed Irfan.
mohammed irfan
Greenhorn

Joined: Feb 11, 2013
Posts: 2
Thnq Campbell Ritchie...!!!
 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
 
subject: Permutations