Generate points sorted by distance

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

[the cyclist]

Here is an example of a vector of length N, with M elements:

v = [zeros(1,N-M+1) 1:M-1];

I am guessing this is not what you mean. I suggest you add enough detail (including the typical sizes of M and N) for us to understand what you really need.

[kamesh iyer]

say N =[ 0.74 -0.74 2.33 -2.33]

I want to generate all possible vectors of length 8 with the elements of N (repetetion allowed). And in this process the vectors should be generated in ascending order of their distance from origin (i.e. 2 norm)

In my case N may contain upto 10-12 elements and the dimension of the required vector may go upto 20-30. But generally N will have about 6-7 elements and the length of the required vectors will be around 10

[Image Analyst]

I have trouble thinking in dimensions above 3. 4 is hard and 30 dimensions is nearly impossible for me. Even in 2 dimensions, the number of vectors of length 8 away from a point is infinite - basically it would be every single point along the circumference of a circle of radius 8, which is an infinite number of points. I'm not sure why you say there will only be 6-7 points. Can you elaborate with a simple 2D example?

[the cyclist]

I think "length 8" here refers to numel=8, not "physical" length. Still, it is still not clear to me what is wanted.

[Image Analyst]

Ah, I think you're right. Looks like it would require some kind of nested for loop code where the number of for loops is equal to the number of elements in N so that you iterate over every one concatenating as you go and bailing out once a given vector that you're building up hits a length of 8. But then there are others that you won't have made so that vector of 8 may show up multiple times and you'd have to remove duplicates because of that. But if you had 4 elements you'd never get more than 4 in the output so you'd need at least 8 for loops. Gets tricky. Maybe might need randperm or nchoosek or some such function to do it some more clever way.

[the cyclist]

OK, I think maybe I get what you want. N is the input vector you specified. You want to generate all possible vectors V, where V obeys the following constraints: (1) the number of elements of V is equal to M (e.g. M=8), and (2) each element of V is a member of N (but repeats are allowed).

Furthermore, you want the list of vectors V to be sorted by distance, where the distance is the Euclidean distance of V from the origin.

So, in your example, two possible valid output vectors would be:

V{1} = [0.74 0.74 0.74 0.74 0.74 0.74 0.74 0.74]

and

V{2} = [0.74 0.74 0.74 0.74 0.74 0.74 0.74 2.33]

and in this case V{1} would come before V{2} because it is closer to the origin.

Does that sound like a correct restatement of your problem?

[kamesh iyer]

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]

@the cyclist.... your last comment correctly identifies my problem

Answer 1

[Walter Roberson]

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.

[kamesh iyer]

i just need a few thousand of these vectors of minimum length

[Walter Roberson]

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.