Given $n$ unique items and an $m^{th}$ normalised value, compute $m^{th}$ permutation without factorial expansion

We know that the number of permutations possible for $ n$ unique items is $ n!$ . We can uniquely label each permutation with a number from $ 0$ to $ (n!-1)$ .

Suppose if $ n=4$ , the possible permutations with their labels are,

0:  1234 1:  1243 2:  1324 3:  1342 4:  1432 5:  1423 6:  2134 7:  2143 8:  2314 9:  2341 10: 2431 11: 2413 12: 3214 13: 3241 14: 3124 15: 3142 16: 3412 17: 3421 18: 4231 19: 4213 20: 4321 21: 4312 22: 4132 23: 4123 

With any well defined labelling scheme, given a number $ m, 0 \leq m < n!$ , we can get back the permutation sequence. Further, these labels can be normalised to be between $ 0$ and $ 1$ . The above labels can be transformed into,

0:       1234 0.0434:  1243 0.0869:  1324 0.1304:  1342 0.1739:  1432 0.2173:  1423 0.2608:  2134 0.3043:  2143 0.3478:  2314 0.3913:  2341 0.4347:  2431 0.4782:  2413 0.5217:  3214 0.5652:  3241 0.6086:  3124 0.6521:  3142 0.6956:  3412 0.7391:  3421 0.7826:  4231 0.8260:  4213 0.8695:  4321 0.9130:  4312 0.9565:  4132 1:       4123 

Now, given $ n$ and $ m^{th}$ normalised label, can we get the $ m^{th}$ permutation while avoiding the expansion of $ n!$ ? For example, in the above set of permutations, if we were given the $ m^{th}$ normalised label to be $ 0.9$ , is it possible to get the closest sequence 4312 as the answer without computing $ 4!$ ?

Knowing the expansion of a function, how can we find its expansion using the inverse of x? [migrated]

If we have a function like:

$ $ \text{f[x$ \_$ ]:=}\sum _{i=0}^{\infty } a_ix^i$ $

where we can find / know the $ a_i$ coefficients, but not really for which function it will converge.

How can we find $ f[x]$ but using the inverse of $ x$ instead? Something like this?

$ $ \text{f[x$ \_$ ]:=}\sum _{i=0}^{\infty } \frac{b_i}{x^i}$ $

The main problem is that the first form of $ f[x]$ does not converge properly for positive values greater than one, since it comes from a Taylor series.

Algorithm: turining a fraction into a decimal expansion string

I already asked this question over on Mathematics and got the suggestion to ask it here.

So I’m basicly implementing a number type that can represent all fractions and was working on an algorithm to compute the decimal expansion for said fractions.

Let’s say we have the reduced fraction $ \frac{n}{m}$ . For converting is into it’s decimal expansion I have now two algorithms.

The first algorithm is simply sing long division to caluclate the decimal expansion up to a given number of decimal places.

The second is:

Let be $ a \in \{1,2,\ldots\}$ a specifier for accuracy.

Calculate: $ $ \begin{align} p &= \lceil \log_{10}(m) \rceil + a \\ f &= \lfloor \frac{10^p}{m} \rfloor \\ v &= n \cdot f \end{align} $ $ Then in $ v$ insert the decimal comma at the correct place or add 0. with leading zeros.

Which works good but it is hard to control the accuarcy with $ a$ . For example if I have the fraction $ \dfrac{884279719003555}{281474976710656} \approx \pi$ then I get:

 a | dec. exp. ---|--------------------------------      v acc 0  1 | 3.0949790165124425        v acc 1  2 | 3.13919300246262025         v acc 1  3 | 3.14096156190062736              v acc 7  8 | 3.14159264580768862709685               v acc 8  9 | 3.14159265288192637912529                   v acc 12 10 | 3.141592653589350154328134                   v acc 12 11 | 3.141592653589350154328134                   v acc 12 12 | 3.141592653589350154328134                      v acc 15 f  = 3.1415926535897931159979634...  pi = 3.1415926535897932384626433... 

So its seams I can controll with $ a$ that at least $ a-1$ decimal places are correct.

But I’m not sure if this will alwasy be the case.

Also I benchmarked both algorithms, and the second is more than 5 times faster. So I really want it to be controllable.

| Method |       Mean |    Error |   StdDev | |--------|-----------:|---------:|---------:| |  first | 4,929.2 ns | 24.34 ns | 20.33 ns | | second |   848.8 ns |  4.00 ns |  3.54 ns | 

So my question basicly is does anybody have suggestion on improving the algorithm or is maybe another algorithm that does the job even better (a.i. fast)?

The accounting Method analysis for table expansion by tripleling instead of doubling an array

If we double the array every time we get the amortized cost of 3n or 3$ if you prefer.

I was wondering what would it be if we tripled the array size instead of doubling it.

The rational between the 3$ cost for every insertion is as follow:

  • 1 dollar for the insertion of an element.
  • 1 dollar is saved for when it will have to move itself to the new array with double the size
  • 1 dollar paying for another element then itself when transfer will be required.

I can’t seem to find the cost for an array that triple each time.

Fourier expansion of inner product mod 2

I’m trying to read Ryan O’Donnell’s book “Analysis of Boolean Functions” and I’m stuck on this one part of an exercise:

  • Compute the Fourier expansion of the indicator function mod 2 function $ \mathrm{IP}_{2n}: \mathbb{F}_2^n \rightarrow \{-1,1\}$ , defined by $ \mathrm{IP}_{2n}(x_1,\ldots,x_n,y_1,\ldots,y_n) = (-1)^{x\cdot y}$

Any hints/tips?

Series expansion of explicit functions

For the following input,

zv[u_, v_] :=   v + zv1[ u, v]/u; mvu[u, v] := D[zv[u, v], u]; Series[mvu[u, v], {u, 0, 1}] 

the output is

-(zv1[0,v]/u^2)+1/2 zv1^(2,0)[0,v]+1/3 u zv1^(3,0)[0,v]+O[u^2] 

I want the series expansion without expansion of zv1[u, v] around 0 (basically the output should be

 zv1^(1,0)[u,v]/u - zv1[u,v]/u^2 

Is there a general method to do this?

Simplify a series expansion including Trigonometric expressions

I have an expression like:

Maf P \[Omega]m Sin[P t \[Omega]m] ((3 Vm)/(\[Pi] R) + \!\( \*UnderoverscriptBox[\(\[Sum]\), \(k = 1\), \(n\)]\(- \*FractionBox[\(6\  \*SuperscriptBox[\((\(-1\))\), \(k\)]\ Vm\ Cos[     k\ p\ t\ w]\), \(\((\(-\[Pi]\) + 36\  \*SuperscriptBox[\(k\), \(2\)]\ \[Pi])\)\  \*SqrtBox[\( \*SuperscriptBox[\(R\), \(2\)] +  \*SuperscriptBox[\(k\), \(2\)]\  \*SuperscriptBox[\(L\), \(2\)]\  \*SuperscriptBox[\(p\), \(2\)]\  \*SuperscriptBox[\(w\), \(2\)]\)]\)]\)\)) 

and I like to expressions like Sin[k p t w + P t [Omega]m] and Sin[k p t w – P t [Omega]m] automatically

view selector expansion

Sharepoint 2013 question.

After some searching on here I have figured out that what I am trying to exapand is called the “list view selector”. Currently all of my views are within the ellipsis and I would like to have them expanded as seen in the picture below. Agreements and Deeds are listed outside of the ellipsis. How can you expand the list view bar ‘out’ or ‘across’ the page insted of using the ellipsis?

I have tried a few different settings within the app to no success.

List View –> All of the toolbar settings

Disable to Re-enable view view selector menu.

enter image description here

Breadth-first traversal: difference between generation and expansion

Romanian map

The question here is to find a path from A(rad) to B(ucharest). I’ll be using the initials of the cities in the picture instead of their full names.

Some ground-rules: we’re traversing in alphabetical order. And traversal must stop once the goal node has been generated, not expanded. This last part is where I feel like I’m not completely understanding what is being asked.

So the solution given is: Arad, Sibiu, Timisoara, Zerind, Fagaras, Bucharest.

What I think the solution is as follows: we’re at A so A has been “generated”. And then we expand A, giving us: A, S, T, Z. Since the goal node hasn’t been generated we start with S. Expanding S gives us F and R (no goal node yet) and then we expand T giving us L following which Z is expanded giving us O. So far we have A, S, T, Z, F, R, L, O. Now, going alphabetically, we go to F for expansion. This gives us B and this is where the traversal should stop.

So my solution is A, S, T, Z, F, R, L, O, B.

Can you tell me where I’m going wrong and why the given solution (as opposed to my solution) is correct?