531 Reputation

18 years, 326 days

Impressively subtle...

I hadn't thought about the \$ operator's action and merely assumed it would create two separate Matrix objects.  Thank you, Joe.  ArrayTools:-Copy now works as intended.

You win this round, Maple!

Impressively subtle...

I hadn't thought about the \$ operator's action and merely assumed it would create two separate Matrix objects.  Thank you, Joe.  ArrayTools:-Copy now works as intended.

You win this round, Maple!

Unclear...

Perhaps I spoke too quickly.  What I should have said is that the following procedure always (for n>1) returns 1:

P:=proc(n)
local M,N,r;
randomize();
M,N:=Matrix(n,n,1)\$2:
r:=0;

while has(M,1) do
r:=r+1;
N:=M;
M[rand(1..n)(),rand(1..n)()]:=0;
if M=N then return r;fi;
od:
return M;
end proc:

If the line "N:=M;" Is changed to "ArrayTools:-Copy(M,N);", the procedure will still return 1.  If the "M=N" in the if statement is replaced with "LinearAlgebra:-Equal(M,N)", the procedure will still return 1.  If the if statement is removed, the procedure will (eventually) return a zero matrix of size n-by-n.

In these procedures I'm working with, "N:=M" and "ArrayTools:-Copy" are functionally equivalent; N appears to simply be a pointer, and is updated whenever M is updated.  This particularly does not seem to be intended behavior of ArrayTools:-Copy.

Yes, I would like Maple to be more efficient in its calculations, but for the time being Maple simply isnt acting the way I expect it to.

Unclear...

Perhaps I spoke too quickly.  What I should have said is that the following procedure always (for n>1) returns 1:

P:=proc(n)
local M,N,r;
randomize();
M,N:=Matrix(n,n,1)\$2:
r:=0;

while has(M,1) do
r:=r+1;
N:=M;
M[rand(1..n)(),rand(1..n)()]:=0;
if M=N then return r;fi;
od:
return M;
end proc:

If the line "N:=M;" Is changed to "ArrayTools:-Copy(M,N);", the procedure will still return 1.  If the "M=N" in the if statement is replaced with "LinearAlgebra:-Equal(M,N)", the procedure will still return 1.  If the if statement is removed, the procedure will (eventually) return a zero matrix of size n-by-n.

In these procedures I'm working with, "N:=M" and "ArrayTools:-Copy" are functionally equivalent; N appears to simply be a pointer, and is updated whenever M is updated.  This particularly does not seem to be intended behavior of ArrayTools:-Copy.

Yes, I would like Maple to be more efficient in its calculations, but for the time being Maple simply isnt acting the way I expect it to.

Interesting...

I don't play around with has() very much.  I tried it at first in this procedure, and it has worked thusfar.  These are interesting considerations to keep in mind.  Thank you for the insight, Joe :)

Interesting...

I don't play around with has() very much.  I tried it at first in this procedure, and it has worked thusfar.  These are interesting considerations to keep in mind.  Thank you for the insight, Joe :)

This is why I love this board...

If I'm unaware of a command, someone else might be able to enlighten me :)  Thank you, I will look into the ArrayTools and LinearAlgebra packages for copying and comparing the matricies.

Currently, my procedure is more or less a "brute force" solution to a problem (mostly a programming problem that I took up because it amused me), and definitely not an elegant one.  There are many improvements I am looking to make.

There are certain situations in which my loop may become "stuck" and cycle infinitely without finding a solution.  This is due to my naive approach to solving the problem.  Think of this problem as similar to mapping out possible moves in a chess game:  The argument A contains the current state of the board.  Information in the array z lists possible "moves" or "new positions" grouped by row and column.  If certain positions must be taken, that is marked in M (an entry in M is given a value other than 1), and then possible moves in z are removed if they do not match certain non-1 values in M.  Not every setup A leads, in this manner, to a unique solution.  I'd like to catch those situations and end the loop.  This catch will be most helpful only while I'm debugging/improving the code.

The matrix M is updated entry by entry twice each loop: first by row, then by column.  Think of Sudoku, or placing numbers in a magic square; if a number is placed in a position due to conditions forced upon it by the row its in, possible entries in that column will be influenced.  Currently, there is no interaction between the rows and columns--possibly the main reason my code can land in infinite loops--that is to say I need a scheme to check whether or not a certain possible configuration of row i would force illegal configurations in column j.  While the updates are "separately" upon each entry, it's handled with broad strokes using andmap commands on z (in an attempt to handle z "in place"), and would be hard to track.

This is why I love this board...

If I'm unaware of a command, someone else might be able to enlighten me :)  Thank you, I will look into the ArrayTools and LinearAlgebra packages for copying and comparing the matricies.

Currently, my procedure is more or less a "brute force" solution to a problem (mostly a programming problem that I took up because it amused me), and definitely not an elegant one.  There are many improvements I am looking to make.

There are certain situations in which my loop may become "stuck" and cycle infinitely without finding a solution.  This is due to my naive approach to solving the problem.  Think of this problem as similar to mapping out possible moves in a chess game:  The argument A contains the current state of the board.  Information in the array z lists possible "moves" or "new positions" grouped by row and column.  If certain positions must be taken, that is marked in M (an entry in M is given a value other than 1), and then possible moves in z are removed if they do not match certain non-1 values in M.  Not every setup A leads, in this manner, to a unique solution.  I'd like to catch those situations and end the loop.  This catch will be most helpful only while I'm debugging/improving the code.

The matrix M is updated entry by entry twice each loop: first by row, then by column.  Think of Sudoku, or placing numbers in a magic square; if a number is placed in a position due to conditions forced upon it by the row its in, possible entries in that column will be influenced.  Currently, there is no interaction between the rows and columns--possibly the main reason my code can land in infinite loops--that is to say I need a scheme to check whether or not a certain possible configuration of row i would force illegal configurations in column j.  While the updates are "separately" upon each entry, it's handled with broad strokes using andmap commands on z (in an attempt to handle z "in place"), and would be hard to track.

Interesting...

Thank you, Joel. :)  Your code looks beautiful; however, without the Iterator module, your techniques will have to remain unused in my code for some time.  Your example using 6 and 18, while illustrative, is not actually expected to come up often in practice using this code.  I would look forward to implementing your procedures at some point to help to expand past the "typical" problems I'm working on.

I've long been aware that mutable data structures scale much more favorably than non-mutable ones, but I'm not very used to implementing them.  Are there any particular resources for learning these techniques that you might know of?

Now that I've overcome the main speed hurdle of the program, I'm running into interesting memory/assignment issues in Maple.  I may start another threat about that.

Interesting...

Thank you, Joel. :)  Your code looks beautiful; however, without the Iterator module, your techniques will have to remain unused in my code for some time.  Your example using 6 and 18, while illustrative, is not actually expected to come up often in practice using this code.  I would look forward to implementing your procedures at some point to help to expand past the "typical" problems I'm working on.

I've long been aware that mutable data structures scale much more favorably than non-mutable ones, but I'm not very used to implementing them.  Are there any particular resources for learning these techniques that you might know of?

Now that I've overcome the main speed hurdle of the program, I'm running into interesting memory/assignment issues in Maple.  I may start another threat about that.

My mistake...

Sorry, I read that reply in haste and assumed that he was talking about my lists and not Doug's code.

While this is a beautiful solution and I do thank Doug (and the rest of you) for the tips, I still need the lists themselves.  I was inspired and able to find my own solution before testing Doug's method.  My code currently produces fully-formatted lists (I manipulate the list of permutations after they are generated) in approximately the same time as Doug's code take to produce his list of locations  (both clocked in at approximately 0.063 seconds).

My mistake...

Sorry, I read that reply in haste and assumed that he was talking about my lists and not Doug's code.

While this is a beautiful solution and I do thank Doug (and the rest of you) for the tips, I still need the lists themselves.  I was inspired and able to find my own solution before testing Doug's method.  My code currently produces fully-formatted lists (I manipulate the list of permutations after they are generated) in approximately the same time as Doug's code take to produce his list of locations  (both clocked in at approximately 0.063 seconds).

Permutations, not choices...

It would be convenient; however, I need all the elements in my list.  See my reply to Doug for an example.

Permutations, not choices...

It would be convenient; however, I need all the elements in my list.  See my reply to Doug for an example.

Typo...

My apologies, Doug.  I had meant no two positive integers adjacent to.  For example when n=k=2, the initial list is [1,2,0,0] and all the permutations are:

[[1, 2, 0, 0], [1, 0, 2, 0], [1, 0, 0, 2], [2, 1, 0, 0], [2, 0, 1, 0], [2, 0, 0, 1], [0, 1, 2, 0], [0, 1, 0, 2], [0, 2, 1, 0], [0, 2, 0, 1], [0, 0, 1, 2], [0, 0, 2, 1]]

Of these results, only [1,0,2,0], [1,0,0,2], and [0,1,0,2] are desired.

Yes, I've been playing with procedures to place k 0's into a list of the first n positive integers.  I was going to say how this seemed a daunting task, but while I was writing this post inspiration struck:

myp2 := proc(n,k)
local L,i;

L:=[ListTools:-Join([i\$i=1..n],0)];
for i from k-(n-1) to 1 by -1 do
L := ListTools:-MakeUnique( [seq( seq(op([L[j][1..m]),0,op(L[j][m+1..-1])],m=0..nops(L[j]) ),j=1..nops(L) )] );
od:

return L;
end proc:

Thank you for pointing out the ListTools:-Sorted command.  That inspired me to look in the ListTools package for an "insert" command, when I found Join.  Since I couldn't in 30 seconds a command to insert an element into a list, I created that sequence command above to simply produce all results from inserting a 0 into any position in the list.  (e.g.  [1,2]  ->  [[0,1,2], [1,0,2], [1,2,0]]).  Though there is a lot of waste in this command, it tackles the case where n=6 and k=8 in about 0.094 seconds.  This is much better than the several minutes I was able to pare this time down to last night before ultimately going to bed.

 1 2 3 4 5 6 7 Last Page 1 of 9
﻿