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

 Number Theory Number Theory Math Forum

 May 2nd, 2017, 01: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 01:57 AM.
May 2nd, 2017, 03:46 AM   #2
Senior Member

Joined: Jun 2014
From: USA

Posts: 363
Thanks: 26

Quote:
 Originally Posted by stt 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 by AplanisTophet; May 2nd, 2017 at 03:55 AM.

 May 2nd, 2017, 04: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
 May 2nd, 2017, 05:48 AM #4 Senior Member   Joined: Jun 2014 From: USA Posts: 363 Thanks: 26 Maybe you'll find this helpful: c++ - Understanding Recursion to generate permutations - Stack Overflow
 May 2nd, 2017, 07: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, 07: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, 09:13 AM   #7
Math Team

Joined: Oct 2011

Posts: 12,398
Thanks: 829

Quote:
 Originally Posted by stt 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?

 May 2nd, 2017, 11:42 AM #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, 12:21 PM   #9
Math Team

Joined: Oct 2011

Posts: 12,398
Thanks: 829

Quote:
 Originally Posted by stt >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.

 May 3rd, 2017, 10:18 AM #10 Newbie   Joined: Sep 2014 From: Kiev Posts: 10 Thanks: 0 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.

 Tags >, adjacent, difference, find, number, numbers, sequences

,

Училка в своем разговоре намекает на секс

Click on a term to search for related topics.
 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post DaphneV Probability and Statistics 2 December 11th, 2016 07:08 PM r-soy Probability and Statistics 3 October 14th, 2013 12:50 AM aprilautumn1234 Algebra 2 August 18th, 2013 08:32 PM sharp Elementary Math 7 October 30th, 2010 08:52 AM aprilautumn1234 Calculus 1 December 31st, 1969 04:00 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top