My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Thanks Tree1Thanks
Reply
 
LinkBack Thread Tools Display Modes
May 2nd, 2017, 01:53 AM   #1
stt
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.
stt is offline  
 
May 2nd, 2017, 03:46 AM   #2
Senior Member
 
Joined: Jun 2014
From: USA

Posts: 308
Thanks: 21

Quote:
Originally Posted by stt View Post
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.
AplanisTophet is offline  
May 2nd, 2017, 04:39 AM   #3
stt
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<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[i] that is added (s[i+1] +k+j) and again taking to recursive function. Are there other suggestions?
stt is offline  
May 2nd, 2017, 05:48 AM   #4
Senior Member
 
Joined: Jun 2014
From: USA

Posts: 308
Thanks: 21

Maybe you'll find this helpful:

c++ - Understanding Recursion to generate permutations - Stack Overflow
AplanisTophet is offline  
May 2nd, 2017, 07:16 AM   #5
stt
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.
stt is offline  
May 2nd, 2017, 07:20 AM   #6
stt
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?
stt is offline  
May 2nd, 2017, 09:13 AM   #7
Math Team
 
Joined: Oct 2011
From: Ottawa Ontario, Canada

Posts: 10,471
Thanks: 693

Quote:
Originally Posted by stt View Post
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?
Denis is offline  
May 2nd, 2017, 11:42 AM   #8
stt
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?
stt is offline  
May 2nd, 2017, 12:21 PM   #9
Math Team
 
Joined: Oct 2011
From: Ottawa Ontario, Canada

Posts: 10,471
Thanks: 693

Quote:
Originally Posted by stt View Post
>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.
Denis is offline  
May 3rd, 2017, 10:18 AM   #10
stt
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.
stt is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

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 07:08 PM
From numbers 1 to 10 find the probability the number chosen r-soy Probability and Statistics 3 October 14th, 2013 12:50 AM
finding a tan function that helps me find the adjacent side aprilautumn1234 Algebra 2 August 18th, 2013 08:32 PM
Find two numbers where difference is 20 & the sum is -4 sharp Elementary Math 7 October 30th, 2010 08:52 AM
finding a tan function that helps me find the adjacent side aprilautumn1234 Calculus 1 December 31st, 1969 04:00 PM





Copyright © 2017 My Math Forum. All rights reserved.