How find all number sequences where the difference between adjacent numbers >= k

stt

Sep 2014
10
0
Kiev
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:
Jun 2014
650
54
USA
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.
I believe you mean that you need to find all of the different orderings (aka, permutations) of a finite set $n$ of positive integers such that, if $x$ is the difference between any two adjacent numbers in the ordering, then $|x| \geq |k|$.

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:

stt

Sep 2014
10
0
Kiev
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<n-k+;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 that is added (s[i+1] +k+j) and again taking to recursive function. Are there other suggestions?
 

stt

Sep 2014
10
0
Kiev
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.
 

stt

Sep 2014
10
0
Kiev
I am not very inclusive on english calculation theory abbreviation so what is $x$, $x, \qeg?
 

Denis

Math Team
Oct 2011
14,592
1,026
Ottawa Ontario, Canada
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.
That's somewhat unclear...
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?
 

stt

Sep 2014
10
0
Kiev
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?
 

Denis

Math Team
Oct 2011
14,592
1,026
Ottawa Ontario, Canada
>And there could be not 5 numbers but 280 or 82000 and higher.

No limit on n? Are you serious?

>And if k is also high enough the calculations gets higher more.

Disagree. The higher k is, the lesser the number of solutions.

>If you defined 184 variants for 1..5 numbers >have you done it manually or programmatically?

Wrote program. Easy to set up program, but n needs to be
reasonable, since there are as many loops as n.
Good luck.
 

stt

Sep 2014
10
0
Kiev
Yes you are right. I mean higher (n-k) 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 pseudo-code 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.