Algorithm to find the next number in a sequence of numbers?
The next number is 486
.
The sequence is *3, *4.
Every odd index is multiplied by 4:
5 20 80 320 1280
Every even index is multiplied by 3:
2 6 18 54 162
Thus, 486
is the next number. :-)
Find next number in a sequence
This question has been answered before: Removing duplicate values from a PowerShell array
Lots of great answer options, but basically:
$Used = $Used | select -uniq
or another option$Used | sort -uniq
How to get next number in sequence in R
By the power of maths!
x1 <- c(3,7,13,21)
dat <- data.frame(x=seq_along(x1), y=x1)
predict(lm(y ~ poly(x, 2), data=dat), newdata=list(x=5:15))
# 1 2 3 4 5 6 7 8 9 10 11
# 31 43 57 73 91 111 133 157 183 211 241
When dealing with successive differences that change their sign, the pattern of output values ends up switching from decreasing to increasing:
x2 <- c(37,26,17,10)
dat <- data.frame(x=seq_along(x2), y=x2)
predict(lm(y ~ poly(x,2), data=dat), newdata=list(x=1:10))
# 1 2 3 4 5 6 7 8 9 10
#37 26 17 10 5 2 1 2 5 10
-(11) -(9) -(7) -(5) -(3) -(1) -(-1) -(-3) -(-5)
-2 -2 -2 -2 -2 -2 -2 -2
As a function:
seqNext <- function(x,n) {
L <- length(x)
dat <- data.frame(x=seq_along(x), y=x)
unname(
predict(lm(y ~ poly(x, 2), data=dat), newdata=list(x=seq(L+1,L+n)))
)
}
seqNext(x1,5)
#[1] 31 43 57 73 91
seqNext(x2,5)
#[1] 5 2 1 2 5
This is also easily extensible to circumstances where the pattern might be n
orders deep, e.g.:
x3 <- c(100, 75, 45, 5, -50)
diff(x3)
#[1] -25 -30 -40 -55
diff(diff(x3))
#[1] -5 -10 -15
diff(diff(diff(x3)))
#[1] -5 -5
seqNext <- function(x,n,degree=2) {
L <- length(x)
dat <- data.frame(x=seq_along(x), y=x)
unname(
predict(lm(y ~ poly(x, degree), data=dat), newdata=list(x=seq(L+1,L+n)))
)
}
seqNext(x3,n=5,deg=3)
#[1] -125 -225 -355 -520 -725
How to get the next number in a sequence
If you do not maintain a counter table, there are two options. Within a transaction, first select the MAX(seq_id)
with one of the following table hints:
WITH(TABLOCKX, HOLDLOCK)
WITH(ROWLOCK, XLOCK, HOLDLOCK)
TABLOCKX + HOLDLOCK
is a bit overkill. It blocks regular select statements, which can be considered heavy even though the transaction is small.
A ROWLOCK, XLOCK, HOLDLOCK
table hint is probably a better idea (but: read the alternative with a counter table further on). The advantage is that it does not block regular select statements, ie when the select statements don't appear in a SERIALIZABLE
transaction, or when the select statements don't provide the same table hints. Using ROWLOCK, XLOCK, HOLDLOCK
will still block insert statements.
Of course you need to be sure that no other parts of your program select the MAX(seq_id)
without these table hints (or outside a SERIALIZABLE
transaction) and then use this value to insert rows.
Note that depending on the number of rows that are locked this way, it is possible that SQL Server will escalate the lock to a table lock. Read more about lock escalation here.
The insert procedure using WITH(ROWLOCK, XLOCK, HOLDLOCK)
would look as follows:
DECLARE @target_model INT=3;
DECLARE @part VARCHAR(128)='Spine';
BEGIN TRY
BEGIN TRANSACTION;
DECLARE @max_seq INT=(SELECT MAX(seq) FROM dbo.table_seq WITH(ROWLOCK,XLOCK,HOLDLOCK) WHERE model=@target_model);
IF @max_seq IS NULL SET @max_seq=0;
INSERT INTO dbo.table_seq(part,seq,model)VALUES(@part,@max_seq+1,@target_model);
COMMIT TRANSACTION;
END TRY
BEGIN CATCH
ROLLBACK TRANSACTION;
END CATCH
An alternative and probably a better idea is to have a counter table, and provide these table hints on the counter table. This table would look like the following:
CREATE TABLE dbo.counter_seq(model INT PRIMARY KEY, seq_id INT);
You would then change the insert procedure as follows:
DECLARE @target_model INT=3;
DECLARE @part VARCHAR(128)='Spine';
BEGIN TRY
BEGIN TRANSACTION;
DECLARE @new_seq INT=(SELECT seq FROM dbo.counter_seq WITH(ROWLOCK,XLOCK,HOLDLOCK) WHERE model=@target_model);
IF @new_seq IS NULL
BEGIN SET @new_seq=1; INSERT INTO dbo.counter_seq(model,seq)VALUES(@target_model,@new_seq); END
ELSE
BEGIN SET @new_seq+=1; UPDATE dbo.counter_seq SET seq=@new_seq WHERE model=@target_model; END
INSERT INTO dbo.table_seq(part,seq,model)VALUES(@part,@new_seq,@target_model);
COMMIT TRANSACTION;
END TRY
BEGIN CATCH
ROLLBACK TRANSACTION;
END CATCH
The advantage is that fewer row locks are used (ie one per model in dbo.counter_seq
), and lock escalation cannot lock the whole dbo.table_seq
table thus blocking select statements.
You can test all this and see the effects yourself, by placing a WAITFOR DELAY '00:01:00'
after selecting the sequence from counter_seq
, and fiddling with the table(s) in a second SSMS tab.
PS1: Using ROW_NUMBER() OVER (PARTITION BY model ORDER BY ID)
is not a good way. If rows are deleted/added, or ID's changed the sequence would change (consider invoice id's that should never change). Also in terms of performance having to determine the row numbers of all previous rows when retrieving a single row is a bad idea.
PS2: I would never use outside resources to provide locking, when SQL Server already provides locking through isolation levels or fine-grained table hints.
Algorithm to find the next number in a sequence
What you want to do is called polynomial interpolation. There are many methods (see http://en.wikipedia.org/wiki/Polynomial_interpolation ), but you have to have an upper bound U on the degree of the polynomial and at least U + 1 values.
If you have sequential values, then there is a simple algorithm.
Given a sequence x1, x2, x3, ..., let Delta(x) be the sequence of differences x2 - x1, x3 - x2, x4 - x3, ... . If you have consecutive values of a degree n polynomial, then the nth iterate of Delta is a constant sequence.
For example, the polynomial n^3:
1, 8, 27, 64, 125, 216, ...
7, 19, 37, 61, 91, ...
12, 18, 24, 30, ...
6, 6, 6, ...
To get the next value, fill in another 6 and then work backward.
6, 6, 6, 6 = 6, ...
12, 18, 24, 30, 36 = 30 + 6, ...
7, 19, 37, 61, 91, 127 = 91 + 36, ...
1, 8, 27, 64, 125, 216, 343 = 216 + 127, ...
The restriction on the number of values above ensures that your sequence never becomes empty while performing the differences.
Related Topics
Retrieve Oracle Last Inserted Identity
R: [Unixodbc][Driver Manager]Can't Open Lib 'SQL Server':File Not Found
SQL Server: Calculating Date Ranges
Oracle Convert Timestamp with Timezone to Date
How to Create "Upcoming Birthdays" Module in Rails
How to Compare Two Columns for Equality in SQL Server
Ora-01861: Literal Does Not Match Format String
How to Do Select Unique with Linq
How to Properly Add Brackets to SQL Queries with 'Or' and 'And' Clauses by Using Arel
Count(Id) VS. Count(*) in MySQL
Oracle Date To_Char('Month Dd, Yyyy') Has Extra Spaces in It
How to Execute SQL Query Without Displaying Results
Rails .Where() Query Not Working
SQL Combine Two Columns in Select Statement
Entity Framework Skip/Take Is Very Slow When Number to Skip Is Big