Carl Love

Carl Love

28015 Reputation

25 Badges

12 years, 293 days
Himself
Wayland, Massachusetts, United States
My name was formerly Carl Devore.

MaplePrimes Activity


These are replies submitted by Carl Love

@achreftabet if we let k = i + j, then goes from 0 to n, and j = k - i. Then the sum can be obtained as 

add(add(a[i, k-i]*x^i*y^(k-i), i= 0..k), k= 0..n)

This assumes that n has a definite nonnegative value at the time the command is executed.

I didn't see your presumably deleted follow-up question, although I can see some possible loose ends in my Answer above. So, if you're having any trouble with that Answer, please ask here.

@sursumCorda I wonder what you mean by saying that `$` is a "lower-level command" (as compared to seq). If you mean simply that it has fewer options than seq, then that is true. But I can"t think of any other way that it could be considered lower level. 

I think that `$` is higher level because it allows for the abstract representation of infinite sequences and sequences with an indefinite number of terms. (Admittedly, those are quite easy things to do.) I make the formal analogy "`$` is to seq as sum is to add."

If you'd post a worksheet showing the error, there's a good chance that I could figure out the problem without even needing to unpack my computer, which'd be useful for me at the moment because I'm driving (at a rest stop at the moment).

@Rakshak As I said, you could plot the polar jets with plots:-tubeplot (which'll give you the most flexibility for color, etc.), or plots:-spacecurve, or plot3d with option style= wireframe. Then assemble all those static plots into a single static plot with plots:-display, and then plots:-animate with plottools:-rotate as shown above.

@acer IMO, if one is using 1D-input, then the expression-form for-while-do-until loop offers the greatest flexibility:

  • has a bona fide assignable return value;
  • can be used inside other expressions;
  • allows any extra statements inside without changing the return value and without changing the displayed values (unless that is desired);
  • allows any of the control structures that an ordinary do loop allows: whileuntil, multilevel break and next;
  • no detectable efficiency differences compared with seq or elementwise; in particular, expression sequences are built in linear, not quadratic, time.

Example:

Bools:= (
     for x in [0,1,2] do
         es1:= "extra statement 1";
         #Handle true/false/FAIL trichotomy: 
         if (b:= is(x in RealRange(Open(0), infinity))) then
             es2:= "extra statement 2"; 
             yes 
         elif b = FAIL then  #See 10th and 13th paragraphs of "Description" on the
             undecidable     #help page ?assume
         else
             es3:= "extra 3"; 
             no 
         fi 
     until b = FAIL
);
                     Bools := no, yes, yes

Indeed, this is the finest looping construct that I've ever seen in any language. Bravo, Maple kernel developers!

@Carlos36r printlevel is an all-or-nothing thing pretty much only suitable for debugging. It'll show the results of all statements executed at the given level or lower. Assignments to a for loop index are considered statements for this purpose, and, of course, that's useful information for debugging. 

There are several things that you could do instead:

1. Wrap the for loop in parentheses (only works in 1D-input AFAIK):

(for x in [0,1,2] do if is(x in RealRange(Open(0), infinity)) then yes else no fi od)  
                         
no, yes, yes

2. Use elementwise operators instead of a loop:

`if`~(is~([0,1,2], RealRange(Open(0), infinity)), yes, no)[]
                         no, yes, yes

3. Use seq (prefix-form looping operator):

seq(`if`(is(x in RealRange(Open(0), infinity)), yes, no), x= (0,1,2))  
                         
no, yes, yes

and others.

@vs140580 

[Moderator's comment: This Reply refers to a Reply that has been deleted.]

What you have written immediately above is highly specific to circulant graphs, whereas the rest of this thread is "pure" general combinatorics. Thus, if you'd like for these specific circulant-graph issues to be addressed, you should start a new Question thread. You've used circulant graphs as examples elsewhere is this thread; that's fine. However, in your most-recent Reply, they are not examples but rather the main issue.

Also, like I said before, please put the relevant parts of the text from your PDFs directly in your MaplePrimes's posts. If, in addition to that, you also want to attach the PDFs, that's fine.

@vs140580 You asked:

  • Which copy of C_4 represents with respect to which vertex if that can be told it will be great

If you could describe a method by which that can be known, then I'll include it.

  • Now put a new G and a new H it is taking sometime attached the same code with the new G and H

As I said, the method that I showed in the worksheet immediately above was not meant to be efficient. Its only purpose was for you to verify that its results were correct before I started working on a more-efficient version.

It's utterly impossible to use that worksheet on the problem that you're currently trying. You should kill it as soon as possible. It'll surely run out of memory and crash before finding a single cover. Here's why: |S| = 200 and n=10 (so, I guess that this is the example with which you started this thread). So, the number of n-subsets of S is binomial(200,10) = 22451004309013280 = 2.2 * 10^16 = 22 quadrillion. The worksheet tries to generate all those subsets before checking any of them.

  • Is it possible to print each IC cover set as it comes , as full excecution may take time I dont know if it is possible

In the code in the Answer (where G = K[n]), that's not possible because all the covers are built at the same time (with a loop that goes from 2 to n). In other words, the construction is "breadth first". That was the main thing that I did to improve the efficiency. Any branches that show violations of the singleton-intersection rule are pruned as soon as possible. This leads to a great reduction of the number of n-subsets of S that need to be checked. 

@vs140580 In order to make sure that I understand your requirements, I need you to verify the correctness of the following solution to your example of embedding C[4] in K[2,2,2]. I am not proposing this as an efficient solution technique; I just need to know whether its final result is correct before proceeding. This worksheet runs in under 5 seconds, and the result is 8 isomorphism covers.

restart:

Automorphs:= (G::Graph)->
local A:= op(4,G), n:= numelems(A), V:= [$n], p, E:= {seq}((op@`{}`~)~(V, A));
    {seq}(subs(V=~ p, E), p= combinat:-permute(n))
:

GT:= GraphTheory:  C:= combinat:

n:= 6:

H:= GT:-Graph([$n], {{1,2}, {2,3}, {3,4}, {4,1}}); #C[4]

GRAPHLN(undirected, unweighted, [1, 2, 3, 4, 5, 6], Array(1..6, {(1) = {2, 4}, (2) = {1, 3}, (3) = {2, 4}, (4) = {1, 3}, (5) = {}, (6) = {}}), `GRAPHLN/table/1`, 0)

G:= GT:-CompleteGraph(2,2,2); #K[2,2,2]

GRAPHLN(undirected, unweighted, [1, 2, 3, 4, 5, 6], Array(1..6, {(1) = {3, 4, 5, 6}, (2) = {3, 4, 5, 6}, (3) = {1, 2, 5, 6}, (4) = {1, 2, 5, 6}, (5) = {1, 2, 3, 4}, (6) = {1, 2, 3, 4}}), `GRAPHLN/table/7`, 0)

E:= GT:-Edges(G);

{{1, 3}, {1, 4}, {1, 5}, {1, 6}, {2, 3}, {2, 4}, {2, 5}, {2, 6}, {3, 5}, {3, 6}, {4, 5}, {4, 6}}

S:= select(s-> s subset E, Automorphs(H)):

E:= `{}`~(E) union {{}}:

IC:= select(s-> (p-> `intersect`(p[]))~(C:-choose(s,2)) = E, C:-choose(S,n));

{{{{1, 3}, {1, 4}, {3, 5}, {4, 5}}, {{1, 3}, {1, 5}, {2, 3}, {2, 5}}, {{1, 4}, {1, 6}, {2, 4}, {2, 6}}, {{1, 5}, {1, 6}, {3, 5}, {3, 6}}, {{2, 3}, {2, 4}, {3, 6}, {4, 6}}, {{2, 5}, {2, 6}, {4, 5}, {4, 6}}}, {{{1, 3}, {1, 4}, {3, 5}, {4, 5}}, {{1, 3}, {1, 5}, {2, 3}, {2, 5}}, {{1, 4}, {1, 6}, {2, 4}, {2, 6}}, {{1, 5}, {1, 6}, {4, 5}, {4, 6}}, {{2, 3}, {2, 4}, {3, 6}, {4, 6}}, {{2, 5}, {2, 6}, {3, 5}, {3, 6}}}, {{{1, 3}, {1, 4}, {3, 5}, {4, 5}}, {{1, 3}, {1, 6}, {2, 3}, {2, 6}}, {{1, 4}, {1, 5}, {2, 4}, {2, 5}}, {{1, 5}, {1, 6}, {3, 5}, {3, 6}}, {{2, 3}, {2, 4}, {3, 6}, {4, 6}}, {{2, 5}, {2, 6}, {4, 5}, {4, 6}}}, {{{1, 3}, {1, 4}, {3, 5}, {4, 5}}, {{1, 3}, {1, 6}, {2, 3}, {2, 6}}, {{1, 4}, {1, 5}, {2, 4}, {2, 5}}, {{1, 5}, {1, 6}, {4, 5}, {4, 6}}, {{2, 3}, {2, 4}, {3, 6}, {4, 6}}, {{2, 5}, {2, 6}, {3, 5}, {3, 6}}}, {{{1, 3}, {1, 4}, {3, 6}, {4, 6}}, {{1, 3}, {1, 5}, {2, 3}, {2, 5}}, {{1, 4}, {1, 6}, {2, 4}, {2, 6}}, {{1, 5}, {1, 6}, {3, 5}, {3, 6}}, {{2, 3}, {2, 4}, {3, 5}, {4, 5}}, {{2, 5}, {2, 6}, {4, 5}, {4, 6}}}, {{{1, 3}, {1, 4}, {3, 6}, {4, 6}}, {{1, 3}, {1, 5}, {2, 3}, {2, 5}}, {{1, 4}, {1, 6}, {2, 4}, {2, 6}}, {{1, 5}, {1, 6}, {4, 5}, {4, 6}}, {{2, 3}, {2, 4}, {3, 5}, {4, 5}}, {{2, 5}, {2, 6}, {3, 5}, {3, 6}}}, {{{1, 3}, {1, 4}, {3, 6}, {4, 6}}, {{1, 3}, {1, 6}, {2, 3}, {2, 6}}, {{1, 4}, {1, 5}, {2, 4}, {2, 5}}, {{1, 5}, {1, 6}, {3, 5}, {3, 6}}, {{2, 3}, {2, 4}, {3, 5}, {4, 5}}, {{2, 5}, {2, 6}, {4, 5}, {4, 6}}}, {{{1, 3}, {1, 4}, {3, 6}, {4, 6}}, {{1, 3}, {1, 6}, {2, 3}, {2, 6}}, {{1, 4}, {1, 5}, {2, 4}, {2, 5}}, {{1, 5}, {1, 6}, {4, 5}, {4, 6}}, {{2, 3}, {2, 4}, {3, 5}, {4, 5}}, {{2, 5}, {2, 6}, {3, 5}, {3, 6}}}}

 

Download IsoCovers.mw

Also, please post the text from your PDFs directly in MaplePrimes. If you want to also attach the PDF, that's okay, but I'll like the text (regardless of its formatting) to be in MaplePrimes.

@Carl Love By implementing a large number of small efficiencies, I've made IsoCovers twice as fast as the version that I posted yesterday. The new code is in the Answer immediately above.

@acer Thanks. I agree, and I edited my Answer accordingly. And I know that the job can be done with a single pair of quotes. Stylistically, I prefer separate pairs for the suffixed and x.

@Carl Love Here is an example of the set sizes involved in my IsoCovers procedure. The large sets are processed with Iterators, so memory is not an issue, only time.

Suppose that H is a simple 3-cycle and 4 isolated vertices. So n |V| = 7 and m = 3K[7] has binomial(7,2) = 21 edges. This set of edges is called E. So, there are binomial(21,3) = 1330 candidate subsets of E to check for isomorphism with H. Clearly, the number of 3-cycles in K[7] is binomial(7,3) = 35, so this is the size of S, the set of isomorphs of H. So the number of candidates for the final set is binomial(35, 7) = 6,724,520. For each of those, we need to check the 21 pairwise intersections.

@vs140580 Here is that program, for what it's worth. The sizes of the sets involved are enormous, so this is only practical for very small n.

IsoCovers:= proc(H::Graph) 
uses GT= GraphTheory, It= Iterator, C= combinat;
local
    n:= GT:-NumberOfVertices(H), V:= [$n], m:= GT:-NumberOfEdges(H),
    E:= GT:-Edges(GT:-CompleteGraph(n)), s, S, J, P
;
    S:= {
        for J in It:-Combination(binomial(n,2), m) do
            s:= E[[seq](J+~1)];
            if GT:-IsIsomorphic(H, GT:-Graph(V, s)) then s else fi
        od
    };
    {
        for J in It:-Combination(nops(S), n) do
            s:= S[[seq](J+~1)];
            P:= (p-> `intersect`(p[]))~(C:-choose(s,2));
            if nops~(P) = {1} and `union`(P[]) = E then s else fi
        od
    }
end proc
:           
GT:= GraphTheory:
H:= GT:-Graph([$4], {{1,2}, {1,3}, {2,3}});
H := Graph 7: an undirected graph with 4 vertices and 3 edge(s)

IsoCovers(H);
     {{{{1, 2}, {1, 3}, {2, 3}}, {{1, 2}, {1, 4}, {2, 4}}, 
       {{1, 3}, {1, 4}, {3, 4}}, {{2, 3}, {2, 4}, {3, 4}}}}

 

@vs140580 A correction for your line

ListTools:-Categorize((x, y) ->(( x[1] = y[1]) and numelems(select(member,x,y))=1), L)

is

ListTools:-Categorize((x,y)-> x[1] = y[1] and nops(x intersect y) = 1, L)

You may consider the returned singleton sublists as irrelevant; if so, they can be removed by

remove(x-> nops(x)=1, [%])

First 51 52 53 54 55 56 57 Last Page 53 of 708