Generate points sorted by distance

2 次查看（过去 30 天）
kamesh iyer
kamesh iyer 2012-2-20
编辑： Walter Roberson 2013-12-9
I am stuck with the following problem:
I have to generate different vectors of length N using M elements (repetition is allowed). However, the vectors should be generated in ascending order of their distance form origin.
Sorting of points after generating them is not practically possible because of the large number of possible combination and also because of large values of N and M. Please help me with this problem.
Thanks
  8 个评论
显示 6更早的评论
kamesh iyer
kamesh iyer 2012-2-20
I'll make it more clear
say N=[1 2]
using the elements of N i.e. 1 and 2 i will generate all possible vectors of length/dimension 3.
So number of possible vectors = (2)^3 = 8
1 1 1
1 1 2
1 2 1
1 2 2
2 1 1
2 1 2
2 2 1
2 2 2
I would like to generate these vectors in ascending order of their distance from origin. Therefore, [1 1 1] will be generated first, then [1 1 2] and [1 2 1] and [2 1 1] will be generated and so on.
I wish to do the same with more elements in N and for higher dimensions. I know that for higher dimensions all the vectors can not be saved. So i want to save only a few thousand of the possible vectors having lesser distance from origin or i can say that i wish to discard the vectors which are relatively far away from the origin.
kamesh iyer
kamesh iyer 2012-2-20
@the cyclist.... your last comment correctly identifies my problem

请先登录，再进行评论。

请先登录，再回答此问题。

回答（1 个）

Walter Roberson
Walter Roberson 2012-2-20
Repetitions are allowed, so you are talking about length(N)^dimension different possible vectors.
At 10 elements in N and a length of 20, that would be 10^20 vectors, which would be approximately 8*10^11 gigabytes (half that if you can make do with single precision.) There is no possible way you are going to be able to store that many values and it is unlikely that any time this century there would be a computer fast enough to list the elements within a single human life span.
  2 个评论
kamesh iyer
kamesh iyer 2012-2-20
i just need a few thousand of these vectors of minimum length
Walter Roberson
Walter Roberson 2012-2-20
编辑：Walter Roberson 2013-12-9
See my generalized algorithm https://groups.google.com/group/comp.lang.c/browse_thread/thread/d98842738fa27a55/2f6d5ff877063de1 and see Chris Torek's refinement to numeric values. I have made other references to this technique over the years under the key word "odometer".
You would want a modification to the pure routine listed there because you want the lowest norms. The lowest norms are those generated by starting with a matrix that is all (identically) the lowest possible value, then selecting the next lowest value and sliding it through each possible position. For each remaining small value which is less than sqrt(2) times the second smallest value, slide that small value through each possible position. When you run out of values which are less than sqrt(2) times the second smallest value, switch to having two copies of that second smallest value and creating the vectors with each of the unique permutations of that pair. Then look to see if there are values greater than sqrt(2) times the second smallest value but less than sqrt() of the squares of the second and third smallest values; if so, slide each of those values solo through each possible position. That done, pair the second and third smallest values through all the unique permutations. The logic beyond this point is left as an exercise to the reader.
The point: there is a deterministic way of generating the vectors with the smallest norms, in a perfectly enumerable way (you could create a bijection between the vectors and the natural numbers.) The amount of storage required is quite small for the generation process; storage of the results is a different matter.

请先登录，再进行评论。

类别

在 Help Center 和 File Exchange 中查找有关 Logical 的更多信息

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by