First question. Okay I have this problem that I've been trying to figure out for a while. I'm writing a computer program I need to quickly calculate the permutations of a set with 'n' elements with a maximum offset of 'x' from their original position.
Say a have a set of four letters (A, B, C, D) and a maximum offset of 2, these would be valid:
ABCD original set obviously valid
BACD valid
BCAD also valid
BCDA
would be invalid because A is in the 4th column and it can only be in the first three columns(max of 2 from original column 1)
DABC
would be invalid because of D for the same reason
What would be the formula to find the number of possible permutations and could you explain to me in laymans terms how this is so(not the best with math)? I assume it would be n! - (something to do with the number of columns an element couldn't exist in). Thanks in advance!
As stated in my comment, counting these is not trivial (in the sense of some simple closed-form).
In the case of your example, this is OEIS A002524. You can take a look at the references there (and/or in the link in my comment) for the mathematical details.
The Kløve paper goes into great detail, the Lehmer paper is also detailed, but only sketches some of the proofs. There are also links to tables for the particular case of your example going up to lengths of 400, same for the related sequences at OEIS for maximum displacement of 3, 4, ... (I think OEIS has none past displacement 9).
Bottom line: You can use permanents of specifically formed matrices, generating functions, or more esoteric means outlined in the references.
The numbers grow quite quickly - here's a snippet done in Mathematica for lengths up to 12 with maximum allowed displacement up to length-1:
This took a few seconds to calculate using non-compiled code on a netbook, so I'd imagine the same on one of my workstations using C/Fortran would be a few hundredths of a second.
I did not investigate too deeply on efficient algorithms to generate such permutations, but coding up a quick-and-dirty in Mathematica produces results for the 10 length / 5 maximum displacement case in a few seconds, again non-compiled and on a netbook, so I'd venture under a tenth of a second using a real machine and compiled code.
(This was coded as a simple recursion, taking the allowable positions for the first element, appending the complement of "taken" positions from the allowable positions for the second element... recursed to the Nth element position).
Using it against your example results in:
Update: Per your comment request, here's the Mathematica snippet to generate these, caveat again this is in no way researched for efficiency - it was barfed out Q&D. If you don't know Mathematica, might not make any sense, if so comment and I'll "unroll" it to p-code.
The $[4,2]$ above are the length and max. displacement arguments, output is the mappings of element to position:
Update: Sketch of the generator as per comment request.
OK, a reminder again, this method was a quick&dirty - there are undoubtedly more efficient means to do this (though I doubt hugely so, since the only "excess" work done here is the occasional probe that shows an element has no available valid positions.) My gut feeling is that any more efficient means would only really benefit at sizes where generating all valid combos would become unrealistic/unusable.
So, we work on a list of evolving valid sequences of positions. We start with a list of an empty list {{}}.
Now, for each list of the top-level list of lists, we replace it with a list that contains any prior positions, appending each valid new element's position.
So, for your example, the top-level list would become {{1},{2},{3}}, since those are the only valid positions the first element of a combination can take (these are just the element position -/+ the allowed offset, clipped to stay within the range of 1 to the eventual total length.)
So, at this point, we've got all the valid positions for the first element, so we repeat the above for the second element for each of those lists. Let's take the {1} list. We know the second element in your example can be any position from 1 to 4 (2 -/+2, clipped). But for this list, 1 is already used earlier in the list, so the valid positions are 2,3,4. So we generate new lists replacing the {1} list with {1,2},{1,3},and {1,4}.
We do this for all of the current lists in the top-level list, getting a new top-level list of {{1,2},{1,3},{1,4},{2,1},{2,3},{2,4},{3,1},{3,2},{3,4}}.
Repeating this process until we've reached the desired total length (4) gives us the position mapping shown earlier.
You can choose to use recursion or nested iteration - whatever best fits your style and the language in use.
If that's not clear, feel free to comment.