自留地

def ExcelColumns(num):
    res = ''
    while num > 0:
        res = chr(ord('A') + ((num-1) % 26)) + res
        num = (num-1) / 26
    return res
    
if __name__ == '__main__':
    all_columns = [ExcelColumns(i) for i in range(1000)]
    print all_columns[1:]

LDA 着实 带领着 Topic model 火了一把。

但是其实我们华人世界内，也不乏好汉，不过呢，都在UIUC，Prof. Zhai的小组里。
他们关于Topic model的大多数工作，都是基于PLSA的变形，然后EM求解。
这里面，他们有两点使用的出神入化，第一点就是先验概率的使用；第二点就是EM的各种变形了，regularized EM。。。
他们组有一个很大的特点，就是问题新，写作特别流畅。
不愧是华人IR第一组。
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
那么如何切入他们组的工作呢？
我这里说一下我自己的经验，按照此经验学习，能够保证你看懂他们的论文。
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
基础篇：概率、PLSA、EM
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
如果大家想要学习PLSA及EM，我推荐Prof. Zhai的一个很好的课程：
http://sifaka.cs.uiuc.edu/course/410s09/schedule.html
恩，在这个页面中，有三个国宝级别的note，对于KL-divergence retrieval、PLSA、EM介绍得简明透彻，读了之后，我只能说一个“牛”。。。
Note on KL-div Retrieval Model;
Note on EM ;
PLSA note
大家最好把这些课件ppt都看了
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
模型基础篇
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
ChengXiang Zhai, Atulya Velivelli, Bei Yu, A cross-collection mixture model for comparative text mining
这篇论文是之后很多的论文的具体应用，其中它提出来的第一个简单模型，配上先验信息的使用，是后面很多论文的一个套路。

Yue Lu, ChengXiang Zhai. Opinion Integration Through Semi-supervised Topic Modeling
这篇论文是上面那个论文的一个应用，但是公式推导极为清晰
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
模型变种篇
Qiaozhu Mei, Xu Ling, Matthew Wondra, Hang Su, ChengXiang Zhai, Topic Sentiment Mixture: Modeling Facets and Opinions in Weblogs
把这个模型看懂了，那么PLSA之类的topic model，你算是过关了。
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
EM进化篇
Tao Tao, ChengXiang Zhai, Regularized Estimation of Mixture Models for Robust Pseudo-Relevance Feedback
对EM感兴趣的同学可以尝试看这篇论文
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
不多说，人家有论文为证：

Yue Lu, ChengXiang Zhai, Neel Sundaresan, Rated Aspect Summarization of Short Comments
Maryam Karimzadehgan, ChengXiang Zhai, Geneva Belford, Multi-Aspect Expertise Matching for Review Assignment
Deng Cai, Qiaozhu Mei, Jiawei Han, ChengXiang Zhai, Modeling Hidden Topics on Document Manifold
Yue Lu, ChengXiang Zhai. Opinion Integration Through Semi-supervised Topic Modeling
Qiaozhu Mei, Deng Cai, Duo Zhang, ChengXiang Zhai. Topic Modeling with Network Regularization
Qiaozhu Mei, Xuehua Shen, and ChengXiang Zhai, Automatic Labeling of Multinomial Topic Models
Qiaozhu Mei, Xu Ling, Matthew Wondra, Hang Su, ChengXiang Zhai, Topic Sentiment Mixture: Modeling Facets and Opinions in Weblogs
Tao Tao, ChengXiang Zhai, Regularized Estimation of Mixture Models for Robust Pseudo-Relevance Feedback
ChengXiang Zhai, Atulya Velivelli, Bei Yu, A cross-collection mixture model for comparative text mining
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

就写这么多了，下次介绍LDA的应用

from ：http://secs.ceas.uc.edu/~franco/C511/html/Scheme/ycomb.html

In this file we derive the Y combinator, one of the fundamental results of recursive procedure theory. You already know that in some cases it is not necessary to give a procedure a name. For example,

((lambda (x) (+ x 1)) 6)

adds 1 to 6 without naming the procedure that does it. But, what about a recursive procedure? For example,

(define fact
    (lambda (n)
      (if (zero? n)
          1
          (* n (fact (- n 1))))))

which computes the factorial of a number n, seems to need the name "fact" so that in the last line of the procedure it can recurse on itself. But, we will see this is not necessary and, in the process, will develop a lot of intuition about using Scheme. We proceed step by step, changing "fact" slightly on each step.

Step 1. The first idea is simply to pass "fact" in as an argument in much the same way that we did for

(define op-maker
    (lambda (op)
      (lambda (x y)
        (op x y))))

The first lambda passes the name of the operation and the second lambda is the nameless operation. Let's try this with "fact". The first attempt is

 (define fact-maker
    (lambda (procedure)
      (lambda (n)
        (if (zero? n)
            1
            (* n (procedure (- n 1)))))))

The idea will be to pass "fact-maker" in through "procedure". Thus, what we would like to do is invoke (fact-maker fact-maker) to produce our nameless (well, almost nameless) factorial procedure. This would allow us to write, for example

  >((fact-maker fact-maker) 5)
  120

But, this doesn't work because "fact-maker" is a procedure which takes as input one argument that is a procedure but "procedure", which is supposed to be identical to "fact", requires a numeric argument. The solution is the following:

 (define fact-maker
    (lambda (procedure)
      (lambda (n)
         (if (zero? n)
             1
             (* n ((procedure procedure) (- n 1)))))))

Try this, for example, with

 >((fact-maker fact-maker) 5)

Well, we got the name out of the body of the procedure but we still have to pass the procedure in and so far we have been using a name to do that. So let's try to get the whole dependence on a name out.

Step 2. Recall we demand that "fact" be identical to (procedure procedure) which in turn must be identical to (fact-maker fact-maker) (recall the example ((fact-maker fact-maker) 5) which gives the same result as (fact 5)). Thus, we can write "fact-maker" in the following way, making use of the result of step 1.

 (define fact
    ((lambda (procedure)
       (lambda (n)
         (if (zero? n)
             1
             (* n ((procedure procedure) (- n 1))))))
     (lambda (procedure)
       (lambda (n)
         (if (zero? n)
             1
             (* n ((procedure procedure) (- n 1))))))))

Try this with >(fact 5)

Consider the following:

  (((lambda (procedure)
      (lambda (n)
        (if (zero? n)
            1
            (* n ((procedure procedure) (- n 1))))))
    (lambda (procedure)
      (lambda (n)
        (if (zero? n)
            1
            (* n ((procedure procedure) (- n 1)))))))
   5)

This produces the factorial of 5 because the procedure which is invoked (the huge mess) is exactly the definition of "fact." But, lo and behold, there is no name for this procedure anywhere!

In what follows, we try to generalize this to all procedures and wind up with the dreaded applicative-order Y-combinator.

Step 3. First, we need to separate out the part that pertains to computing the factorial. The goal is to write this part in one place and when code for other problems is substituted for the factorial code, the result will be a new recursive procedure. This step is a little tricky because we insist on using, with no significant changes, code that was designed assuming a procedure name. The section of factorial code we currently have, from step 2, is

   (define F
    (lambda (n)
      (if (zero? n)
          1

This is different from what we want because it contains a (procedure procedure) where we would like to see a plain old procedure. So, we use a trick to get it out. In general, isn't

  (f arg)

identical to

  ((lambda (x) (f x)) arg) ?

The second statement is a little strange, though, because it makes you pass "arg" into a procedure so that the procedure which would be applied to it anyway is applied. Why do we want to do such a thing? Watch! This means that

  ((procedure procedure) (- n 1))

is the same as

  ((lambda (arg) ((procedure procedure) arg)) (- n 1))

and we substitute this into our current version of F to get

  (define F
    (lambda (n)
      (if (zero? n)
          1
          (* n ((lambda (arg) ((procedure procedure) arg)) (- n 1))))))

How has this helped? Well, the (lambda (arg)...) is ONE procedure and procedures can be passed as arguments so F can be defined as

  (define F
    ((lambda (func-arg)
       (lambda (n)
         (if (zero? n)
             1
             (* n (func-arg (- n 1))))))
     (lambda (arg) ((procedure procedure) arg))))

Yes, it's the same F but the old definition looked like this:

  (define F (lambda (n) ... < procedure >))

and the new definition looks like this:

  (define F ((lambda (func-arg) (lambda (n) ...)) < procedure >))

where < procedure > is the (lambda (arg) ((procedure... ) ...) ...) expression

Step 4. - Now we are ready to take the result of step 3 and apply it to the result of step 2. Writing out the whole thing, we get:

  (define fact
    ((lambda (procedure)
       ((lambda (func-arg)
          (lambda (n)
            (if (zero? n)
                1
                (* n (func-arg (- n 1))))))
        (lambda (arg) ((procedure procedure) arg))))
     (lambda (procedure)
       ((lambda (func-arg)
          (lambda (n)
            (if (zero? n)
                1
                (* n (func-arg (- n 1))))))
        (lambda (arg) ((procedure procedure) arg))))))

You will probably want to study this carefully. Notice the double left parens in front of ((lambda (func-arg)... This is because we are writing

   ...
   ((lambda (func-arg) < body-using-func-arg >) (lambda (arg) ...))

which has the same form as

  ((lambda (arg) ((procedure procedure) arg)) (- n 1))

but is different in that a procedure is passed as an "arg" instead of an integer.

The two expressions beginning with (lambda (func-arg) ...) are exactly the pieces of code that correspond to the factorial code and they are in exactly the right form. So we can get them out of the definition of fact in the following way:

  (define F*
    (lambda (func-arg)
      (lambda (n)
        (if (zero? n)
            1
            (* n (func-arg (- n 1)))))))

  (define fact
    ((lambda (procedure)
       (F* (lambda (arg) ((procedure procedure) arg))))
     (lambda (procedure)
       (F* (lambda (arg) ((procedure procedure) arg))))))

This is significant because we can now use any procedure in place of F* to change functionality to whatever we want. The only problem is that, as written, we still need to name F*. This is easily remedied in the next step.

Step 5. Jackpot! Now we write the dreaded applicative-order Y-combinator:

  (define Y
    (lambda (X)
      ((lambda (procedure)
         (X (lambda (arg) ((procedure procedure) arg))))
       (lambda (procedure)
         (X (lambda (arg) ((procedure procedure) arg)))))))

Notice that the procedure which does our computation is X (we stopped using F* to emphasize this code can be applied to any procedure) and that is passed in as an argument.

Step 6. We can write "fact" in terms of the Y-combinator as follows:

  (define fact (Y F*))

Try >(fact 5) to check the result. For that matter, try >((Y F*) 5). But Y is general and F* is specific to factorial but with no name! If we wrote the whole thing out it would be

  (((lambda (X)
      ((lambda (procedure)
         (X (lambda (arg) ((procedure procedure) arg))))
       (lambda (procedure)
         (X (lambda (arg) ((procedure procedure) arg))))))
    (lambda (func-arg)
      (lambda (n)
        (if (zero? n)
            1
            (* n (func-arg (- n 1)))))))
   5)

Look Ma! No name! Just to show the generality of all this let's use the Y combinator to define another procedure. Say findmax - finding the largest integer in a list.

  (define findmax
    (lambda (l)
      (if (null? l)
          'no-list
          (if (null? (cdr l))
              (car l)
              (max (car l) (findmax (cdr l)))))))

First, create the analog of F* for fact, call it M for max.

  (define M
    (lambda (func-arg)
      (lambda (l)
        (if (null? l)
            'no-list
            (if (null? (cdr l))
                (car l)
                (max (car l) (func-arg (cdr l))))))))

Now try ((Y M) '(4 5 6 3 4 8 6 2)) to see if it works. If you want to build it out it looks like this:

  (((lambda (X)
      ((lambda (procedure)
         (X (lambda (arg) ((procedure procedure) arg))))
       (lambda (procedure)
         (X (lambda (arg) ((procedure procedure) arg))))))
    (lambda (func-arg)
      (lambda (l)
        (if (null? l)
            'no-list
            (if (null? (cdr l))
                (car l)
                (max (car l) (func-arg (cdr l))))))))
   '(4 5 6 3 4 8 6 2))

As an assignment for the interested student, write findamx without using the procedure name "max". Just how many of the remaining names in findmax do you think can be disposed of? Talk about a nameless society...

看到一道题目：12个高矮不同的人,排成两排,每排必须是从矮到高排列,而且第二排比对应的第一排的人高,问排列方式有多少种?

此题本质上与合法出栈序列是一样的，合法解的数目为catalan数：f(n) = C(2n, n) / (n+1)。

如果进一步，求出所有合法的序列，可以参照TAOCP上的结论：若出栈序列合法，则一定不存在   1<=i<j<k<=n，使s[j]<s[k]<s[i]  ：

void GetAllValidSeqs(int *pSeq, const int k, const int n)
{
	if (k == n)
	{
		for (int i=0; i<k; i++)
		{
			cout<<pSeq[i]<<' ';
		}
		
		for (int i=0; i<n-2; ++i)
		{
			for (int j=i+1; j<n-1; ++j)
			{
				if (pSeq[i] > pSeq[j])
				{
					for (int k=j+1; k<n; ++k)
					{
						if(pSeq[k]>pSeq[j] && pSeq[k]<pSeq[i])   
							goto L1;
					}
				}
				
			}
		}
		cout<<" is valid."<<endl;
		return;

L1:		cout<<" is invalid."<<endl;
		return;

	} 
	else
	{
		for (int i=k; i<n; ++i)
		{
			mySwap(pSeq, k, i);
			GetAllValidSeqs(pSeq, k+1, n);
			mySwap(pSeq, k, i);
		}
	}
}

int MaxDistanceOfTree(TreeNodeEx *pRoot)
{
	if (pRoot == NULL)
	{
		return 0;
	}
	stack<TreeNodeEx*> nodeStack;
	TreeNodeEx *pNode = pRoot;
	int nMaxDist = 0;
	while (pNode != NULL || !nodeStack.empty())
	{
		if (pNode != NULL)
		{
			nodeStack.push(pNode);
			pNode = pNode->pLeft;
		} 
		else
		{
			pNode = nodeStack.top();
			nodeStack.pop();
			if (!pNode->visited)
			{
				pNode->visited = true;
				nodeStack.push(pNode);
				pNode = pNode->pRight;
			} 
			else
			{
				pNode->nLeft = (pNode->pLeft == NULL) ? 0 : max(pNode->pLeft->nLeft, pNode->pLeft->nRight) + 1;
				pNode->nRight = (pNode->pRight == NULL) ? 0 : max(pNode->pRight->nLeft, pNode->pRight->nRight) + 1;
				if (pNode->nLeft + pNode->nRight > nMaxDist)
				{
					nMaxDist = pNode->nLeft + pNode->nRight;
				}
				pNode = NULL;
			}
		}
	}

	return nMaxDist;
}

LinkNode* ReverseLink(LinkNode *pLink)
{
	if (pLink->pNext == NULL || pLink == NULL)
		return pLink;
	LinkNode *pHead = ReverseLink(pLink->pNext);
	pLink->pNext->pNext = pLink;
	pLink->pNext = NULL;
	return pHead;

}

LinkNode* ReverseLink(LinkNode *pLink)
{
	if (pLink->pNext == NULL || pLink == NULL)
		return pLink;
	LinkNode *p, *q, *r;
	p = NULL;
	q = pLink;
	r = q->pNext;
	while (r != NULL)
	{
		q->pNext = p;		
		p = q;
		q = r;
		r = r->pNext;

	}
	q->pNext = p;
	return q;
}

void PreTravel(TreeNode *pRoot)
{
	if (pRoot == NULL)
		return;
    stack<TreeNode*> nodeStack;
	nodeStack.push(pRoot);
	cout<<"preTravel:"<<endl;
	while (!nodeStack.empty())
	{
		TreeNode *pNode = nodeStack.top();
		nodeStack.pop();
		cout<<pNode->data<<' ';
		if (pNode->pRight != NULL)
		{
			nodeStack.push(pNode->pRight);
		}
		if (pNode->pLeft != NULL)
		{
			nodeStack.push(pNode->pLeft);
		}
	}
	cout<<endl<<endl;

}

void midTravel(TreeNode *pRoot)
{
	if (pRoot == NULL)
		return;
	stack<TreeNode*> nodeStack;
	TreeNode *pNode = pRoot;
	cout<<"midTravel:"<<endl;
	while (pNode != NULL || !nodeStack.empty())
	{
		if (pNode != NULL)
		{
			nodeStack.push(pNode);
			pNode = pNode->pLeft;
		} 
		else
		{
			pNode = nodeStack.top();
			cout<<pNode->data<<' ';
			nodeStack.pop();
			pNode = pNode->pRight;
		}
	}
	cout<<endl<<endl;
}

void postTravel(TreeNode *pRoot)
{
	if (pRoot == NULL)
		return;
	stack<TreeNode*> nodeStack;
	TreeNode *pNode = pRoot;
	cout<<"postTravel:"<<endl;
	while (pNode != NULL || !nodeStack.empty())
	{
		if (pNode != NULL)
		{
			nodeStack.push(pNode);
			pNode = pNode->pLeft;
		} 
		else
		{
			pNode = nodeStack.top();
			nodeStack.pop();
			if (!pNode->visited)
			{
				pNode->visited = true;
				nodeStack.push(pNode);
				pNode = pNode->pRight;
			} 
			else
			{
				cout<<pNode->data<<' ';
				pNode = NULL;
			}
		}
	}
	cout<<endl<<endl;
}

void layerTravel(TreeNode *pRoot)
{
        if (pRoot == NULL)
		return;
	deque<TreeNode*> nodeDeque;
	nodeDeque.push_back(pRoot);
	cout<<"layerTravel:"<<endl;
	while (!nodeDeque.empty())
	{
		TreeNode *pNode = nodeDeque.front();
		nodeDeque.pop_front();
		cout<<pNode->data<<' ';
		if (pNode->pLeft != NULL)
			nodeDeque.push_back(pNode->pLeft);
		if (pNode->pRight != NULL)
			nodeDeque.push_back(pNode->pRight);
	}
	cout<<endl<<endl;
}

void ConstructTree(int* preSeq, int* midSeq, int treeLen, TreeNode **ppRoot)
{
	if (NULL == preSeq || NULL == midSeq || treeLen <= 0)
		return;
	int nRoot = *preSeq;
	TreeNode *pNode = new TreeNode(nRoot, false, NULL, NULL);
	if(NULL == *ppRoot)
		*ppRoot = pNode;
	int nPos = -1;
	for (int i=0; i<treeLen; ++i)
	{
		if (midSeq[i] == nRoot)
		{
			nPos = i;
			break;
		}
	}
	if (nPos >= treeLen || nPos < 0)
		return;
	ConstructTree(preSeq+1, midSeq, nPos, &pNode->pLeft);
	ConstructTree(preSeq+nPos+1, midSeq+nPos+1, treeLen-nPos-1, &pNode->pRight);

}

void DestroyTree(TreeNode *pRoot)
{
	if (pRoot == NULL)
		return;
	if (pRoot->pLeft != NULL)
	{
		DestroyTree(pRoot->pLeft);
		pRoot->pLeft = NULL;
	}
	if (pRoot->pRight != NULL)
	{
		DestroyTree(pRoot->pRight);
		pRoot->pRight = NULL;
	}
	cout<<"data "<<pRoot->data<<" has been deleted."<<endl;
	delete pRoot;
	pRoot = NULL;
}

题目： 2n个数，一半奇数，一半偶数，设计一个程序让奇数位上的数是奇数，偶数位上的是偶数

要求：时空复杂度尽量低

看到群里发的这个题目，随手写了个一个答案：

def swap(a, i, j): 
    a[i] = a[i] + a[j]
    a[j] = a[i] - a[j]
    a[i] = a[i] - a[j]
        
def Fun():
    the_list = [x for x in range(100)]
    print "orginal:", the_list
    random.shuffle(the_list)
    print "shuffled:", the_list
    i,j = 0,1
    nSwap = 0
    while nSwap < 50 and max(i,j) < 100:
        if the_list[i] % 2 != 0 and the_list[j] % 2 == 0 :
            swap(the_list,i,j)
            i += 2
            j += 2
            nSwap += 1
        elif the_list[i] % 2 == 0 :
            i += 2
        elif the_list[j] % 2 != 0 :
            j += 2
    print "sorted:", the_list

经penny等群友的提醒，优化一下，第二版：

def Fun2():
    the_list = [x for x in range(100)]
    print "orginal:", the_list
    random.shuffle(the_list)
    print "shuffled:", the_list 
    for i,j in zip([pos for pos in range(0,100,2) if (the_list[pos] + pos) % 2 != 0],
                              [pos for pos in range(1,100,2) if (the_list[pos] + pos) % 2 != 0]):
        the_list[i], the_list[j] = the_list[j], the_list[i]
    print "sorted:", the_list

附：penny发了一个点积的优化

A[]={<0,4>,<3,5>,<8,3>}
B[]={<3,5>,<9,3>}

C=A*B = {<3,25>}

for(i=0,j=0;i<lenA&&j<lenB;)
{
	k=0;	
	if(A[i].index == B[j].index)
	{
		C[k].index = A[i].index;
		C[k].value = A[i].value * B[j].value
		k++
	}
	else if(A[i].index < B[j].index)
	{
		i++;
	}
	else if(A[i].index > B[j].index )
	{
		j++;
	}
}

A_I[]={0,3,8}
B_I[]={3,9}
A_V[]={4,5,9}
B_V[]={5,3}
for(i=0,j=0;i<lenA&&j<lenB;)
{
	k=0;
	if(A_I[i] == B_I[j])
	{
		C[k].index = A_I[i];
		C[k].value = A_V[i]*B_V[j];
	}
	else if(A_I[i] < B_I[j])
	{
		i++;
	}
	else
	{
		j++;
	}
}

for(i=0,j=0;i<lenA&&j<lenB;)
{
	k=0;
	i=0;
	j=0;
	bool equal  =  A_I[i] == B_I[j];
	bool smaller=  A_I[i] < B_I[j]; 
	bool bigger =  A_I[i] > B_I[j];
	C[k].index  =  equal*A_I[i];
	C[k].value  =  equal*A_V[i]*B_V[j];
	k+=equal;
	i+=equal;
	j+=equal;
        i+=smaller;
	j+=biger;	
}