
Number Theory Number Theory Math Forum 
 LinkBack  Thread Tools  Display Modes 
May 2nd, 2017, 02:53 AM  #1 
Newbie Joined: Sep 2014 From: Kiev Posts: 10 Thanks: 0  How find all number sequences where the difference between adjacent numbers >= k
There are N natural numbers. I need to find all possible number sets when the difference between adjacent numbers are no less then K, where K is natural number. For example n(1,2,3,4,5). K=2 => {1,3,5,2,4}; {2,4,1,5,2};... The length of resulting set is also n. So I need implement it as some algorithm programmatically, but even do not concieve what appoach and algorithm to apply to take into account all possible number sets? So maybe i could use all possible sets that will be recurrent so I need some time consuming check with FOR cycle, indeed then the first main task how to account all possible ones, when the elements could be recurrent and N could be a big number as K as well.
Last edited by stt; May 2nd, 2017 at 02:57 AM. 
May 2nd, 2017, 04:46 AM  #2  
Senior Member Joined: Jun 2014 From: USA Posts: 320 Thanks: 23  Quote:
If this is to be programmed into a computer, I'd start by computing an array containing all of the different permutations of the set $n$. You'll need an array of size $n!$. Then, run a function that computes the difference between each set of adjacent elements in each permutation. Toss out the permutations where there exists adjacent elements whose difference $x$ is such that $x < k$. Last edited by AplanisTophet; May 2nd, 2017 at 04:55 AM.  
May 2nd, 2017, 05:39 AM  #3 
Newbie Joined: Sep 2014 From: Kiev Posts: 10 Thanks: 0 
I think it is more issue for programming but not for discrete math, as the last allow to find the quantity of such permutation. It was the question for programming. So For cycles should to be. As for me I need outer FOR cycle to iterate since the first number untill last one. Then in the inner FOR cycle began to add/distract to I (current number of outer iteration) the k+j (j=0;j<nk+;j++). Then use this last peace of code/calculation as recursion function and when the lengh of "string" of numbers would be N, then display such found set and continue to next iteration. So it needs some another restrictions to not go out of 0<i=<n. So just such consequtive iteration would avoid recurrence of the same sets. But should it be resolved just with recursion function whose argument would be every element of needed set s[i] that is added (s[i+1] +k+j) and again taking to recursive function. Are there other suggestions?

May 2nd, 2017, 06:48 AM  #4 
Senior Member Joined: Jun 2014 From: USA Posts: 320 Thanks: 23 
Maybe you'll find this helpful: c++  Understanding Recursion to generate permutations  Stack Overflow 
May 2nd, 2017, 08:16 AM  #5 
Newbie Joined: Sep 2014 From: Kiev Posts: 10 Thanks: 0 
Maybe you are correct about permutation indeed my recursion method is not far from this approach. Could it not be avoided without recursion? Supposition about permuttation proves by the number of resulting set that is the same N. Indeed I asked when trying to resolve should I use the probability theory calculations and the answer was unclear and I understood that I do not need permutations, combinations or so there.

May 2nd, 2017, 08:20 AM  #6 
Newbie Joined: Sep 2014 From: Kiev Posts: 10 Thanks: 0 
I am not very inclusive on english calculation theory abbreviation so what is $x$, $x, \qeg?

May 2nd, 2017, 10:13 AM  #7  
Math Team Joined: Oct 2011 From: Ottawa Ontario, Canada Posts: 11,324 Thanks: 728  Quote:
Is N same as n? Assuming it is, and assuming numbers can be repeated (as shown in your example {2,4,1,5,2}) then for 1,2,3,4,5 there would be 184 cases; in increasing order: 001: 1,3,1,3,1 002: 1,3,1,3,5 003: 1,3,1,4,1 004: 1,3,1,4,2 005: 1,3,1,5,1 ...... 180: 5,3,5,1,5 181: 5,3,5,2,4 182: 5,3,5,2,5 183: 5,3,5,3,1 184: 5,3,5,3,5 Is that what is expected?  
May 2nd, 2017, 12:42 PM  #8 
Newbie Joined: Sep 2014 From: Kiev Posts: 10 Thanks: 0 
Yes. N is the n in that case (Nuances of "national" typecasing). And there could be not 5 numbers but 280 or 82000 and higher. And if k is also high enough the calculations gets higher more. So just computer can resolve it indeed it is task for program so it stipulates the complexity. If you defined 184 variants for 1..5 numbers have you done it manually or programmatically?

May 2nd, 2017, 01:21 PM  #9  
Math Team Joined: Oct 2011 From: Ottawa Ontario, Canada Posts: 11,324 Thanks: 728  Quote:
 
May 3rd, 2017, 11:18 AM  #10 
Newbie Joined: Sep 2014 From: Kiev Posts: 10 Thanks: 0 
Yes you are right. I mean higher (nk) the more calculations. And the provisions of "my"task is enough ambigious as for k=2 the solution 1,3,1,3,1 .. is also acceptable. So maybe permutation is not option as solution for such specific algorithm? Could by idea of pseudocode to be applicable? There is also mentioning of iterative not recursive solution for permutation is it far more complex? Anyway for such task I was assigned about 15 minutes  is it reasonable time for the man that did not faced task about permutation before and takiing into account that it was just one of the task and probably not the most difficult.


Tags 
>, adjacent, difference, find, number, numbers, sequences 
Search tags for this page 
Click on a term to search for related topics.

Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Find the number of divisors of 189,720 that are composite numbers?  DaphneV  Probability and Statistics  2  December 11th, 2016 08:08 PM 
From numbers 1 to 10 find the probability the number chosen  rsoy  Probability and Statistics  3  October 14th, 2013 01:50 AM 
finding a tan function that helps me find the adjacent side  aprilautumn1234  Algebra  2  August 18th, 2013 09:32 PM 
Find two numbers where difference is 20 & the sum is 4  sharp  Elementary Math  7  October 30th, 2010 09:52 AM 
finding a tan function that helps me find the adjacent side  aprilautumn1234  Calculus  1  December 31st, 1969 04:00 PM 